title: What's wrong with my (attempted) implementation of iterateM?
body: <p>I would like to implement a function, iterateM, whose type would look like this:</p>
  
  <pre><code>iterateM :: Monad m =&gt; (a -&gt; m a) -&gt; a -&gt; [m a]
  </code></pre>
  
  <p>However, my first go at writing this function:</p>
  
  <pre><code>iterateM f x = f x &gt;&gt;= (\x' -&gt; return x' : iterateM f x')
  </code></pre>
  
  <p>Gives me the error:</p>
  
  <pre><code>Could not deduce (m ~ [])
  from the context (Monad m)
    bound by the type signature for
               iterateM :: Monad m =&gt; (a -&gt; m a) -&gt; a -&gt; [m a]
    at main.hs:3:1-57
    `m' is a rigid type variable bound by
        the type signature for
          iterateM :: Monad m =&gt; (a -&gt; m a) -&gt; a -&gt; [m a]
        at main.hs:3:1
  Expected type: [a]
    Actual type: m a
  In the return type of a call of `f'
  In the first argument of `(&gt;&gt;=)', namely `f x'
  In the expression: f x &gt;&gt;= (\ x' -&gt; return x' : iterateM f x')
  </code></pre>
  
  <p>If I remove my type-signature, ghci tells me the type of my function is:</p>
  
  <pre><code>iterateM :: Monad m =&gt; (a -&gt; [a]) -&gt; a -&gt; [m a]
  </code></pre>
  
  <p>What am I missing here?</p>