On Wed, Sep 26, 2012 at 12:41 AM, <o...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
