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

[wren ng thornton]

On 9/18/12 4:27 AM, oleg at 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