title: The Maybe result from Map.lookup is not type checking with my Monad Transformer stack
body: <p>I am going though the following paper: <a href="https://page.mi.fu-berlin.de/scravy/realworldhaskell/materialien/monad-transformers-step-by-step.pdf" rel="nofollow noreferrer">Monad Transformers Step by Step</a>. In section 2.1 "Converting to Monadic Style", a function is converted to return <code>Value</code> in the <code>Eval1</code> monad. This part of the function doesn't make sense to me:</p>
  
  <pre><code>eval1 env (Var n) = Map.lookup n env
  </code></pre>
  
  <p>The result of that will be <code>Maybe Value</code> however the function's type signature is:</p>
  
  <pre><code>eval1 :: Env → Exp → Eval1 Value
  </code></pre>
  
  <p>The function is failing to type check, and the error seems obvious to me.  Yet the author specifically states that this will work:</p>
  
  <blockquote>
    <p>... 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.</p>
  </blockquote>
  
  <p>The signature for Map.lookup does not look like it is designed to work with any monad:</p>
  
  <pre><code>lookup :: Ord k =&gt; k -&gt; Map k a -&gt; Maybe a
  </code></pre>
  
  <p>Is this paper out of date or am I missing something?  If the paper is in fact out of date, why was <code>lookup</code> changed to only work with <code>Maybe</code>.</p>
  
  <p>Thanks!</p>