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.