The Maybe result from Map.lookup is not type checking with my Monad Transformer stack

12
votes

I am going though the following paper: Monad Transformers Step by Step. In section 2.1 "Converting to Monadic Style", a function is converted to return Value in the Eval1 monad. This part of the function doesn't make sense to me:

eval1 env (Var n) = Map.lookup n env

The result of that will be Maybe Value however the function's type signature is:

eval1 :: Env → Exp → Eval1 Value

The function is failing to type check, and the error seems obvious to me. Yet the author specifically states that this will work:

... the Var case does not need a fromJust call anymore: The reason is that Map.lookup is defined to work within any monad by simply calling the monad’s fail function – this fits nicely with our monadic formulation here.

The signature for Map.lookup does not look like it is designed to work with any monad:

lookup :: Ord k => k -> Map k a -> Maybe a

Is this paper out of date or am I missing something? If the paper is in fact out of date, why was lookup changed to only work with Maybe.

Thanks!

1
haskelldictionarymonadsmonad-transformersmaybe
It's out of date (since containers version 0.2.0.0, from 2008). This method was briefly popular but then went out of style again. See this question, in particular Don Stewart's answer. – Ørjan Johansen
The next time you wonder if an interface has changed, you can usually get the answer by looking at old and new versions on Hackage. – dfeuer

1 Answers

15
votes

Your tutorial is from 2006. It uses a very old version of Data.Map in which lookup's type indeed was:

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

I reckon the change happened because fail is widely considered to be a wart in the Monad class. Returning a Maybe a makes a lookup failure explicit and manageable. Making it implicit by hiding it behind fail just to have a slightly more convenient type is quite dirty IMO. (See also the question linked to by Ørjan.)

You can use this adapted version of lookup to follow along the tutorial:

fallibleLookup :: (Ord k, Monad m) => k -> Map.Map k a -> m a
fallibleLookup k = maybe (fail "fallibleLookup: Key not found") pure . Map.lookup k

Note that with the upcoming release of GHC 8.8 the proper constraint to use on m will be MonadFail rather than Monad.