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

Question

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!

Answer 1

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.