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

[Brian Bloniarz]

How about the following, using difference lists?

> import Control.Arrow
> import qualified Data.DList as D
>
> start = (Nothing, (D.empty, D.empty))
>
> iter (Nothing, (r1, r2)) x = (Just x, (r1, r2))
> iter (Just y, (r1, m)) x =
>     D.list (Nothing, (D.singleton y, D.singleton x))
>            (\r r2 -> let r2' = D.snoc (D.snoc r2 y) x
>                      in  (Nothing, (D.snoc r1 r, r2')))
>            m
>
> inTwain :: [a] -> ([a], [a])
> inTwain = (D.toList *** D.toList) . snd . foldl iter start

There's no recursion besides the fold. Though using difference
lists might be cheating, depending on your definition of
cheating :)

-Brian

> Bonjour café,
> 
> A small puzzle:
> 
> Consider the function inTwain that splits a list of even length evenly 
> into two sublists:
> 
>  > inTwain "Hello world!"
> ("Hello ","world!")
> 
> Is it possible to implement inTwain such that the recursion is done by 
> one of the standard list folds?
> 
> Is there a general way to tell if a problem can be expressed as a fold?
> 
> Thank you,
> 
> Martijn.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_________________________________________________________________
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/20090604/661af3a1/attachment.html