Re: [Haskell-cafe] Church Encoding Function
On 3/10/07, Robert Dockins <[EMAIL PROTECTED]> wrote: 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. They do exist: Initial Algebra Semantics is Enough! Patricia Johann and Neil Ghani. http://crab.rutgers.edu/~pjohann/tlca07.pdf code: http://www.cs.nott.ac.uk/~nxg/Tlca07.hs Jim ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church Encoding Function
On 10/03/07, Joachim Breitner <[EMAIL PROTECTED]> wrote: Is there a name for these functions? "Characteristic Church Encoding Functions" maybe? Are there more than these: Catamorphisms is indeed the name I've heard. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church Encoding Function
On Sat, Mar 10, 2007 at 03:43:41PM +0100, 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? folds (with the arguments flipped) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church Encoding Function
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church Encoding Function
On Sat, Mar 10, 2007 at 03:43:41PM +0100, 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 usually hear "deconstructor". either :: Either a b -> (a -> r) -> (b -> r) -> r > Maybe -- maybe > Bool -- ifthenelse > List -- foldr > (,) -- uncurry > > Just a short idea while waiting at the airport... > > Greetings, > Joachim > > -- > Joachim "nomeata" Breitner > mail: [EMAIL PROTECTED] | ICQ# 74513189 | GPG-Key: 4743206C > JID: [EMAIL PROTECTED] | http://www.joachim-breitner.de/ > Debian Developer: [EMAIL PROTECTED] > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Church Encoding Function
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: Maybe -- maybe Bool -- ifthenelse List -- foldr (,) -- uncurry Just a short idea while waiting at the airport... Greetings, Joachim -- Joachim "nomeata" Breitner mail: [EMAIL PROTECTED] | ICQ# 74513189 | GPG-Key: 4743206C JID: [EMAIL PROTECTED] | http://www.joachim-breitner.de/ Debian Developer: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe