How to takeWhile items in a monad wrapped list

Question

Got a little riddle, I was wondering if you could help me explain.

Define a function that returns a list:

let f = replicate 3 

What we want to do is match this function with an infinite list, combine the results, and then take only those things that match the predicate.

 takeWhile (< 3) $ concatMap f [1..] 

Excellent! This returns [1,1,1,2,2,2] what I want.

Now I want to do something similar, but the f function now completes its results in Monad. In my usecase, this is the IO monad, but this works to discuss my problem:

 let f' x = Just $ replicate 3 x 

For matching and concat, I can use:

 fmap concat $ mapM f' [1..5] 

This returns: Just [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5]

If I want to use takeWhile , this still works:

 fmap (takeWhile (< 3) . concat) $ mapM f' [1..5] 

Which returns: Only [1,1,1,2,2,2]. Excellent!

But, if I create a list by which I map an infinite list, this does not do what I expected:

 fmap (takeWhile (< 3) . concat) $ mapM f' [1..] 

It seems that takeWhile never happens. Somehow, I don't get the lazy calculations that I expected. I lost a little.

Answer 1

The problem is not that fmap + takeWhile does not work with infinite lists enclosed in a monad. The problem is that mapM cannot create an infinite list (at least not in the Maybe monad).

Think about this: if f' returns Nothing for any item in the list, mapM should return Nothing . However, mapM cannot know if this will happen until it calls f' for all elements in the list. Therefore, he needs to iterate over the entire list before he finds out if the result is Nothing or Just . Obviously the problem is with infinite lists.

Answer 2

This should do the trick:

 takeWhileM :: (Monad m) => (a -> Bool) -> [ma] -> m [a] takeWhileM p [] = return [] takeWhileM p (m:ms) = do x <- m if px then liftM (x:) (takeWhileM p ms) else return [] 

See sepp2k answer for an explanation of the causes of laziness. For example, the Identity monad or nun of a non-empty list will not have this problem.

Answer 3

You cannot display an endless list of Maybes. mapM is a map followed by a sequence. Here is the definition of the sequence:

  sequence ms = foldr k (return []) ms
   where
     kmm '= do {x <- m;  xs <- m ';  return (x: xs)}

This shows that the sequence evaluates each monadic value in the list. Since this is an infinite list, this operation will not be completed.

EDIT:

luqui and Carl emphasize that this does not generalize to any monad. To understand why this does not work, perhaps we need to look at the implementation (→ =):

 (>>=) mk = case m of Just x -> kx Nothing -> Nothing 

The important point here is that we make the case on m. This makes m strict because we need to evaluate it to figure out how to proceed. Note that we do not go around x here, so it remains lazy.