[Haskell-cafe] A small puzzle: inTwain as function of foldr
Brian Bloniarz
phunge0 at hotmail.com
Fri Jun 5 22:08:13 EDT 2009
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
More information about the Haskell-Cafe
mailing list