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@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