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

[Brian Bloniarz]

Hi all,

Malcom Wallace wrote:
> Martijn van Steenbergen <martijn at van.steenbergen.nl> 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.

I think this is the essentially the  same solution as the difference-list 
solution I posted before -- same approach, different datastructures.

> > 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
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090605/5ad3ab9b/attachment.html