On 9/18/12 4:27 AM, o...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
