26 Sep
2012
26 Sep
'12
1:06 a.m.
On Wed, Sep 26, 2012 at 12:41 AM,
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