Friday, July 29, 2011

It works this time

When I started learning Haskell I heard that the type system could be used to check all kinds of constraints at compile time -- far beyond just the type of the data. For the most part I have found this not to be the case -- not because the type system can't do these things but because most people who program Haskell are either 1) not leet enough to use it that way (this includes me) or 2) too leet for me to understand their code, so I have no idea what kind of constraints are being checked.

But I did run into a beautiful example using Maps. A Map stores data with ordered keys, so to do that you need an ordering function, and they used the most obvious possible type signature for that ordering:

1 compare :: a -> a -> Ordering

And here's the great thing: the Map consistency cannot possibly be screwed up by using mutable keys.

Ah, but that's easy, you say: just use immutable keys -- make them const. But this is even better: you don't have to use immutable keys. I could use a key like this:

1 data Key = Key { 2 x :: Int 3 , y :: IORef Int 4 }

That's mutable. I can change it. Even while it's being used as a key. But there is no way (and I really hope someone doesn't come and tell me that there is a way because that would make me sad) for compare to see those changes -- because of its type.

In fact you can pack as much mutable state as you want into the Key, and it is partitioned off cleanly from ever affecting the ordering.

But here's what I really love about this: it works because the guys who wrote Map picked the simplest most obvious type for compare. It's the type you'd come up with if someone pointed a gun to your head and said "you have 5 seconds give me the type for compare". They could have written it

1 compare :: (Monad m) => a -> a -> m Ordering

except that that's substantially less obvious and in this case turns out to be undesirable.

It's not always like this. A lot of the standard functions for operating on lists could have been made monadic because they don't need consistency. This is one of those rare beautiful cases of the language working exactly the way it's supposed to.

(In other news, untracked side-effects may be "dangerous" but nothing beats the havoc of using a backtracking monad transformer on the ST monad. Nothing I tell you.)

No comments:

Post a Comment