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

oleg at okmij.org oleg at okmij.org
Tue Sep 18 10:27:36 CEST 2012

There has been a recent discussion of ``Church encoding'' of lists and
the comparison with Scott encoding.

I'd like to point out that what is often called Church encoding is
actually Boehm-Berarducci encoding. That is, often seen

> newtype ChurchList a =
>     CL { cataCL :: forall r. (a -> r -> r) -> r -> r }

(in http://community.haskell.org/%7Ewren/list-extras/Data/List/Church.hs )

is _not_ Church encoding. First of all, Church encoding is not typed
and it is not tight. The following article explains the other
difference between the encodings


Boehm-Berarducci encoding is very insightful and influential. The
authors truly deserve credit.

P.S. It is actually possible to write zip function using Boehm-Berarducci

More information about the Haskell-Cafe mailing list