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