What's wrong with my (attempted) implementation of iterateM?

Question

I would like to implement a function, iterateM, whose type would look like this:

iterateM :: Monad m => (a -> m a) -> a -> [m a]

However, my first go at writing this function:

iterateM f x = f x >>= (\x' -> return x' : iterateM f x')

Gives me the error:

Could not deduce (m ~ [])
from the context (Monad m)
  bound by the type signature for
             iterateM :: Monad m => (a -> m a) -> a -> [m a]
  at main.hs:3:1-57
  `m' is a rigid type variable bound by
      the type signature for
        iterateM :: Monad m => (a -> m a) -> a -> [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 `(>>=)', namely `f x'
In the expression: f x >>= (\ x' -> return x' : iterateM f x')

If I remove my type-signature, ghci tells me the type of my function is:

iterateM :: Monad m => (a -> [a]) -> a -> [m a]

What am I missing here?

Answer 1

What I gather from your signature:

iterateM :: (Monad m) => (a -> m a) -> a -> [m a]

Is that the nth element iterateM f x will be an action that runs f n times. This is very close to iterate, I suspect we can implement it in terms of that.

iterate :: (b -> b) -> b -> [b]

iterate gives us a list of bs, and we want a list of m as, so I suspect b = m a.

iterate :: (m a -> m a) -> m a -> [m a]

Now we need a way to transform f :: a -> m a into something of type m a -> m a. Fortunately, that is exactly the definition of bind:

(=<<) :: (Monad m) => (a -> m b) -> (m a -> m b)

So:

\f -> iterate (f =<<) :: (a -> m a) -> m a -> [m a]

And to get our initial x :: a into the desired m a, we can use return:

return :: (Monad m) => a -> m a

So:

iterateM f x = iterate (f =<<) (return x)

Pointfreeize to taste.

Answer 2

Your recursive use of iterateM is forcing it to be in the list monad. You need to run the iterateM action and return its result.

Try:

iterateM f x = do
      x' <- f x
      xs <- iterateM f x'
      return $ x':xs