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

Brian Bloniarz 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')))
>            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.
> _______________________________________________