What happened to my (attempt) implementation of iterateM?

Question

I would like to implement the iterateM function, the type of which will look like this:

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

However, first of all, I am writing this function:

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

Gives me an error:

 Could not deduce (m ~ []) from the context (Monad m) bound by the type signature for iterateM :: Monad m => (a -> ma) -> a -> [ma] at main.hs:3:1-57 `m' is a rigid type variable bound by the type signature for iterateM :: Monad m => (a -> ma) -> a -> [ma] at main.hs:3:1 Expected type: [a] Actual type: ma In the return type of a call of `f' In the first argument of `(>>=)', namely `fx' In the expression: fx >>= (\ x' -> return x' : iterateM f x') 

If I remove my type signature, ghci will tell me what my function type is:

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

What am I missing here?

Answer 1

What I collect from your signature:

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

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

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

iterate gives us a list of b s, and we need a list of ma s, so I suspect b = ma .

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

Now we need a way to convert f :: a -> ma into something like ma -> ma . Fortunately, this is exactly the definition of bind:

 (=<<) :: (Monad m) => (a -> mb) -> (ma -> mb) 

So:

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

And to get the initial x :: a to the desired ma , we can use return :

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

So:

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

Explain to taste.

Answer 2

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

Try:

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