RE: [Haskell-cafe] A small puzzle: inTwain as function of foldr

Hi all, Malcom Wallace wrote:

Martijn van Steenbergen wrote:

...

But this uses length and init and last all of which are recursive functions. I consider that cheating: only foldr may do the recursion.

I think the key is to pick your intermediate data-structure wisely. A pair of queues would be my choice.

...

unQ (Q begin end) = begin ++ reverse end This might be cheating too? This solution recurses over the input only once, but then you need to recurse over the queue to convert it to a

I think this is the essentially the same solution as the difference-list solution I posted before -- same approach, different datastructures. list. The difference list solution manages to only recurse once, I think. Here's the same solution I posted, with all the difference-list operations inlined:

import Control.Arrow

start = (Nothing, (id, id))

iter (Nothing, (r1, r2)) x = (Just x, (r1, r2)) iter (Just y, (r1, r2)) x = case r2 [] of [] -> (Nothing, (\t -> y:t, \t -> x:t)) r:_ -> let r1' = \t -> r1 (r : t) r2' = \t -> tail (r2 (y:x:t)) in (Nothing, (r1', r2'))

inTwain :: [a] -> ([a], [a]) inTwain = (($[]) *** ($[])) . snd . foldl iter start As you can see, it's building up nested lambdas, adding a new lambda to r1 and r2 on each iteration of the fold. And, on each iteration, it's also applying the function it's built. Basically, it's using the program stack as it's intermediate datastructure. Ugly and inefficient yes, but recursion-free as far as I can see.

Thanks, -Brian P.S. The "walk the list at 2 speeds" trick is very slick. _________________________________________________________________ Windows Live™: Keep your life in sync. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_BR_life_in_synch_062009