<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
</style>
</head>
<body class='hmmessage'>
Hi all,<br><br>Malcom Wallace wrote:<br>> Martijn van Steenbergen <martijn@van.steenbergen.nl> wrote:<br>> <br>> > But this uses length and init and last all of which are recursive <br>> > functions. I consider that cheating: only foldr may do the recursion.<br>> <br>> I think the key is to pick your intermediate data-structure wisely. A<br>> pair of queues would be my choice.<br><br>I think this is the essentially the same solution as the difference-list <br>solution I posted before -- same approach, different datastructures.<br><br>> > unQ (Q begin end) = begin ++ reverse end<br>This might be cheating too? This solution recurses over the input only<br>once, but then you need to recurse over the queue to convert it to a<br>list.<br><br>The difference list solution manages to only recurse once, I think.<br>Here's the same solution I posted, with all the difference-list operations<br>inlined:<br>> import Control.Arrow<br>><br>> start = (Nothing, (id, id))<br>><br>> iter (Nothing, (r1, r2)) x = (Just x, (r1, r2))<br>> iter (Just y, (r1, r2)) x =<br>> case r2 [] of<br>> [] -> (Nothing, (\t -> y:t, \t -> x:t))<br>> r:_ -> let r1' = \t -> r1 (r : t)<br>> r2' = \t -> tail (r2 (y:x:t))<br>> in (Nothing, (r1', r2'))<br>><br>> inTwain :: [a] -> ([a], [a])<br>> inTwain = (($[]) *** ($[])) . snd . foldl iter start<br>As you can see, it's building up nested lambdas, adding a new<br>lambda to r1 and r2 on each iteration of the fold. And, on each<br>iteration, it's also applying the function it's built. Basically, it's<br>using the program stack as it's intermediate datastructure.<br>Ugly and inefficient yes, but recursion-free as far as I can see.<br><br>Thanks,<br>-Brian<br><br>P.S. The "walk the list at 2 speeds" trick is very slick.<br><br /><hr />Windows Live™: Keep your life in sync. <a href='http://windowslive.com/explore?ocid=TXT_TAGLM_WL_BR_life_in_synch_062009' target='_new'>Check it out.</a></body>
</html>