Joachim Breitner's Homepage

Categories

This is a post about the implementation of data types in the programming language Haskell. If you haven’t heard about that, you can proabably safely skip it.

For a while I have been thinking: Isn’t there a way to get rid of the intermediate `Maybe`

construct in a common expression like `fromMaybe default . lookup. `

It seems that a way to do that would be to pass more information to the `Maybe`

-generating function: What to do with a `Just`

-Value, and what to return in case of `Nothing`

. This leads to a new definion of the `Maybe`

data type as a function. Later I discovered that this seems to work for any algebraic data type.

This is probably nothing new, but I was offline at the time of writing, so I didn’t check. This means that this might also be total rubbish. Enjoy.

- “Algebraic Data Type Done Differently” (PDF-File)
- “Algebraic Data Type Done Differently” (Literate Haskell Source / LaTeX Source)

Update: Several responses in the “haskell-cafe”-list told me that I just re-invented Curch-Encoding. Nice :-)

This is, in fact, the standard way of encoding datatypes in the lambda calculus (which has only functions). It's quite flexible, as you'll see if you start playing around.

#1 Dylan Thurston am 2007-03-08T00:06:40+00:00

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.