[Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists
dan.doel at gmail.com
Wed Sep 26 07:06:59 CEST 2012
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 .
More information about the Haskell-Cafe