Friday, February 29, 2008

How I Learned to Stop Worrying And Love Haskell's Type Inference

In developing the HAppS example that I have been posting here, I came upon a problem that gave me new insight to Haskell. I don't think it was a particularly deep insight, but it is significant to me as someone new to the language, and new to type inference.

Consider a user authentication function that retrieves a map from the reader monad, looks up a username, and compares the password retrieved with a passed in parameter. I first implemented this function something like this:

data User = User {
  username :: String,
  password :: String
}

authUser name pass = do
                     u <- liftM (M.lookup name) ask
                     liftM2 (==) (liftM password u) (return pass)

In the process of getting there, I stumbled around rearranging and inserting various liftM calls until I finally got it to work. Many of the reasons behind the type errors still seemed like voodoo to me. And my haphazard approach to fixing them is evident looking at the code. The problem with this function is how it behaves when the username does not exist in the map. A look at the lookup function in Data.Map reveals that it has the following type:

lookup :: (Monad m, Ord k) => k -> Map k a -> m a

The documentation informs us that the function will return the result in a monad or fail if the key isn't in the map. When I originally wrote the function, the significance of this was lost on me. So I didn't pay much attention to it and after trial and error, finally got authUser to compile. Now I needed to figure out how to properly handle the failure of the monad.

The documentation for lookup suggests using the Maybe monad, where fail is defined to be Nothing. So how to get lookup into the Maybe monad? I could have used another function and specified a type declaration, but there had to be a better way. I'm not a fan of type annotations. They seem to clutter up the code too much. After thinking about it for awhile, I finally realized that the call to lookup was being put into the reader monad because that's the monad being used by authUser.

When the lightbulb came on, it was blinding. I just needed to use the result of lookup in a way that forced the Haskell's type inference to put it into the Maybe monad! To do this, all you have to do is compare to Just pass instead of pass. We'll have to lift the password function into the Maybe monad first, but that's not a problem. So the code simplifies to this:

authUser2 name pass = do
  users <- ask
  return $ (Just pass) == liftM password (M.lookup name users)

...which has exactly the desired behavior. If the user isn't found in the map, then the lookup returns Nothing. The lifted password function also returns Nothing, which is then compared to "Just pass". This comparison fails just like we want.

In retrospect, this doesn't seem like a particularly difficult concept to understand. I knew that the type inference engine did this sort of thing with type variables. But I think the many ways of applying this behavior is something not immediately appreciated by programmers coming to Haskell from an imperative background. Conclusion: Haskell's type inference engine is your friend. Instead of viewing it as something getting in the way that must be worked around, try to figure out how you can make it work to your advantage.

6 comments:

Brian said...

Congratulations. This is one of the big steps (IMHO) in learning a strongly-typed functional programming language like Haskell- when you stop fighting the type system and start working with it.

The next step will be when you start swearing at languages that don't have strong static typing and saying things like "All I'm asking for is for the compiler to have some small amount of intelligence so that if it sees me doing something obviously wrong, it'll tell me."

Neil Mitchell said...

Cool :-)

You can actually remove one set of brackets:

return $ Just pass == liftM password (M.lookup name users)

Justin George said...

I ran into this when I was doing type conversions to spit out binary data. I was looking for conversion functions for each type, but there was only one for all of them.

Lightbulb time: It figures out what you want by the type of the other functions. That's when I really started liking it.

mightybyte said...

Brain,

I've already gotten to the point that I'm swearing at Java (used at work) for not having first-class functions. Hopefully I'll hit your next step soon.

Neil,

Someone else pointed out that I could have used asks to avoid the need to bind to users.

authUser2 name pass = asks $ (Just pass ==) . liftM password . M.lookup name

Justin,

And the nice thing is that the other place where you actually specify the type can be "a long ways" from the function that you're actually influencing. I suppose some might argue that this is bad for readability, but it sure is powerful.

Mike Machenry said...

I don't think you should shy away from explicit type declarations so much. When used properly, they can be huge improvement to type errors.

Personally, when programming in Haskell, I annotate all of my top-level functions with an explicit type declaration, and omit types everywhere else, like lambda, let, and where. This gives barriers to how far apart the error you made can be from the location it was report.

I think it also improves readability. A reader doesn't have to do the type inference himself to understand how the function works. I like to have a line of comment and a type annotation for every function.

mightybyte said...

Mike,

Now, two years after I wrote this post, I agree with you completely. Back then, I didn't have a good working knowledge of writing type declarations--especially monadic ones--so sometimes I didn't know what type declaration was needed. Now I write them much more often, sometimes even on inner declarations to help localize errors.