[Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists

[Dan Doel]

On Wed, Sep 26, 2012 at 12:41 AM,  <oleg at okmij.org> wrote:
> First of all, the Boehm-Berarducci encoding is inefficient only when
> doing an operation that is not easily representable as a fold. Quite
> many problems can be efficiently tackled by a fold.

Indeed. Some operations are even more efficient than usually expected
when operating on folds. For instance:

    snoc xs x f = xs f . f x

People often recommend using ([a] -> [a]) for efficiently building up
lists without worrying about introducing O(n^2) costs through bad
associativity, but the Boehm-Berarducci encoding gets you that and
more (map g xs f = xs (f . g) ; map h (map g xs) = \f -> xs (f . g .
h)).

-- Dan