On 9/18/12 4:27 AM, oleg@okmij.org wrote:
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.
I know that Church encodings were explored in the untyped setting (and hence cannot be tight); but I was unaware of a citation for the typed version of the same encoding. I've since corrected the names of the above module. N.B., for folks following along at home, the above module and the Scott version aren't actually in list-extras yet. I just dumped them there for lack of somewhere else to stash the code from last time this comparison came up.
P.S. It is actually possible to write zip function using Boehm-Berarducci encoding: http://okmij.org/ftp/ftp/Algorithms.html#zip-folds
Of course it is; I just never got around to doing it :) -- Live well, ~wren