[Haskell-cafe] Church Encoding Function

[Robert Dockins]

On Saturday 10 March 2007 09:43, Joachim Breitner wrote:
> Hi,
>
> some more ideas following from the last post. I noticed how the function
> Data.Maybe.maybe converts a Haskell Maybe into a Church encoded Maybe.
> Also, the if construct, interpreted as a function, converts a Bool into
> a church encoded Bool.
>
> If lists are encoded as forall b. (a -> b -> b) -> b -> b, then foldr,
> with the right order of arguments, converts a haskell [] to a Church
> encoded List.
>
> Is there a name for these functions? “Characteristic Church Encoding
> Functions” maybe? Are there more than these:

I believe these are the same as catamorphisms.

http://en.wikipedia.org/wiki/Catamorphism

Here is the paper where the term (AFAIK) was coined (although I have to admit 
to having only skimmed it):

http://citeseer.ist.psu.edu/meijer91functional.html


I'm pretty sure you can define a catamorphism for any regular algebraic data 
type.  I'm not 100% sure what the story is for non-regular (AKA nested) 
datatypes.


> Maybe -- maybe
> Bool -- ifthenelse
> List -- foldr
> (,) -- uncurry
>
> Just a short idea while waiting at the airport...
>
> Greetings,
> Joachim