Filter an infinite list of monadic values

Question

Perhaps this is obvious, but I can't seem to figure out how to best filter an infinite list of IO values. Here is a simplified example:

infinitelist :: [IO Int]

predicate :: (a -> Bool)

-- how to implement this?
mysteryFilter :: (a -> Bool) -> [IO a] -> IO [a]

-- or perhaps even this?
mysteryFilter' :: (a -> Bool) -> [IO a] -> [IO a]

Perhaps I have to use sequence in some way, but I want the evaluation to be lazy. Any suggestions? The essence is that for each IO Int in the output we might have to check several IO Int values in the input.

Thank you!

Answer 1

Not doable without using unsafeInterleaveIO or something like it. You can't write a filter with the second type signature, since if you could you could say

unsafePerformIOBool :: IO Bool -> Bool
unsafePerformIOBool m  = case mysteryFilter' id [m] of
    []    -> False
    (_:_) -> True

Similarly, the first type signature isn't going to work--any recursive call will give you back something of type IO [a], but then to build a list out of this you will need to perform this action before returning a result (since : is not in IO you need to use >>=). By induction you will have to perform all the actions in the list (which takes forever when the list is infinitely long) before you can return a result.

unsafeInterleaveIO resolves this, but is unsafe.

 mysteryFilter f [] = return []
 mysteryFilter f (x:xs) = do ys <- unsafeInterleaveIO $ mysteryFilter f xs
                             y <- x
                             if f y then return (y:ys) else return ys

the problem is that this breaks the sequence that the monad is supposed to provide. You no longer have guarantees about when your monadic actions happen (they might never happen, they might happen multiple times, etc).

Lists just do not play nice with IO. This is why we have the plethora of streaming types (Iteratees, Conduits, Pipes, etc).

The simplest such type is probably

data MList m a = Nil | Cons a (m (MList m a))

note that we observe that

[a] == MList Id a

since

toMList :: [a] -> MList Id a
toMList [] = Nil
toMList (x:xs) = Cons x $ return $ toMList xs

fromMList :: MList Id a -> [a]
fromMList Nil = []
fromMList (Cons x xs) = x:(fromMList . runId $ xs)

also, MList is a functor

instance Functor m => Functor (MList m) where
  fmap f Nil = Nil
  fmap f (Cons x xs) = Cons (f x) (fmap (fmap f) xs)

and it is a functor in the category of Functor's and Natural transformations.

trans :: Functor m => (forall x. m x -> n x) -> MList m a -> MList n a
trans f Nil = Nil
trans f (Cons x xs) = Cons x (f (fmap trans f xs))

with this it is easy to write what you want

mysteryFilter :: (a -> Bool) -> MList IO (IO a) -> IO (MList IO a)
mysteryFilter f Nil = return Nil
mysteryFilter f (Cons x xs)
  = do y <- x
       let ys = liftM (mysteryFilter f) xs
       if f y then Cons y ys else ys

or various other similar functions.