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

[oleg at okmij.org]

> Wouldn't you say then that "Church encoding" is still the more appropriate
> reference given that Boehm-Berarducci's algorithm is rarely used? 
>
> When I need to encode pattern matching it's goodbye Church and hello Scott.
> Aside from your projects, where else is the B-B procedure used?

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.

Second, I must stress the foundational advantage of the
Boehm-Berarducci encoding: plain System F. Boehm-Berarducci encoding
uses _no_ recursion: not at the term level, not at the type level.  In
contrast, the efficient for pattern-match encodings need general
recursive types. With such types, a fix-point combinator becomes
expressible, and the system, as a logic, becomes inconsistent.