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

Thomas ten Cate ttencate at gmail.com
Thu Jun 4 12:57:04 EDT 2009

Possible, yes.

Efficient, not really.

> inTwain = foldr (\x (ls, rs) -> if length ls == length rs then (x:ls, rs) else (x:(init ls), (last ls):rs)) ([], [])

I have a hunch that everything that reduces a list to a fixed-size
data structure can be expressed as a fold, simply by carrying around
as much intermediate state as necessary. But I'm too lazy and
inexperienced to prove this.


On Thu, Jun 4, 2009 at 16:22, Martijn van
Steenbergen<martijn at van.steenbergen.nl> wrote:
> 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

More information about the Haskell-Cafe mailing list