[Haskell-cafe] A small puzzle: inTwain as function of foldr
phunge0 at hotmail.com
Thu Jun 4 13:14:36 EDT 2009
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')))
> 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
> 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,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Windows Live™: Keep your life in sync.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe