SwirlyMyself
Categories

2007-03-07T22:24:22+00:00

A different Maybe maybe

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.

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

Filed under: English, Haskell | Flattr this blog | Flattr this post

Comments

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
Another interesting thing about this is that if you think about it a bit, the standard treatment of algebraic datatypes in Haskell/ML is a pretty thin layer on this. Typically, to use values from an algebraic datatype, you have to unpack the data using some sort of a casing construct (either a function call or a "case" statement). In a lambda-calculus reduction, this is just syntactic sugar for building a new pile of closures and passing them to the encoding function of the structure.


Probably a more fruitful way to optimize Maybe (and one that I would hope the compiler already does!) is to use pointer tagging-type tricks. You might be familiar with this already -- essentially, you use the fact that all pointers on a 32-bit architecture have the last two bits set to zero. So, if you set (say) the low bit of a possibly-pointer value to 1, that means that it's something other than a pointer. You can use this to give common constants like [] and Nothing a unique encoding.
#2 Daniel Burrows am 2007-03-10T06:04:37+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.