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

oleg at okmij.org oleg at okmij.org
Wed Sep 26 06:41:46 CEST 2012

> 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.

More information about the Haskell-Cafe mailing list