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 http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html 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 encoding: http://okmij.org/ftp/ftp/Algorithms.html#zip-folds