Filtering a list of monads


I am attempting to filter a list of type: IO [Either a b]

Ideally, I would like to compose filtering function with the following type sig:

(Monad m, Monad m2) => m [m2 a] -> (a -> Bool) -> m [m2 a]

I have tried a lot of combinations of filter, filterM, fmap, and =<< in a vain attempt to lift my predicate into the proper context, but I keep missing the mark - I can achieve m [m a]-> (a -> m Bool)-> m [m a], but since Either and IO are not the same monad, this doesn't seem to do me any good.

This seems like a usecase for 'do notation' , but I've been unable to suss out a way to examine the type signatures of things assigned with the <- operator, and so am left shooting at a moving target.

I am not sure how to compose the function in a way that will make it clear that it's traversing a list containing a instances of a different monad (Either) then the monad that contains the list itself (IO).

What am I missing here?

Show source
| haskell   2017-01-05 17:01 2 Answers

Answers ( 2 )

  1. 2017-01-05 17:01

    Ideally, I would like to compose filtering function with the following type sig:

    (Monad m, Monad m2) => m [m2 a] -> (a -> Bool) -> m [m2 a]

    It can't be done in general, because the Monad interface provides no way to get an a out of an m a. You can get as far as m [m2 Bool] using fmap (fmap (fmap f)) but you need to get the Bool out of the m2 Bool in order to decide whether or not to drop the element.

    Look at it this way. What if the monad in question was Proxy?

    data Proxy a = Proxy  -- one constructor, no fields
    instance Monad Proxy where
        return _ = Proxy
        Proxy >>= _ = Proxy

    You can't look at the Bool inside a Proxy Bool because there's never anything inside it! Given a -> Bool and [Proxy a], how can I be expected to know which elements of the list to drop?

    You can write a function with the following type signature:

    myfilter :: (Functor f, Applicative g) => (a -> Bool) -> f [g a] -> f (g [a])

    Note that the return type is f (g [a]), not f [g a].

    This function uses fmap to go into the outer functor, smashes together the applicative gs in the list, then fmaps once more to filter the results.

    myfilter p = fmap (fmap (filter p) . sequenceA)
  2. 2017-01-05 18:01

    To add to the accepted answer while you may not be able to get the a out of the Monad m, you can get your functions into the Monad m using e.g. liftM. Depending on the inner structure(s) you can still compose usable actions and then finally sequence them in some fashion so the computations 'happen' in the desired fashion.

    To give an example using the problem of IO[Either a b] given as IO[Either Bool Integer]:

    import Control.Monad
    testCase :: IO [Either Bool Integer]
    testCase = return [(Right 1), (Left True), (Right 2), (Left False), (Right 3), (Right 4)]
    liftFilter :: Monad m => (a -> Bool) -> m [a] -> m [a]
    liftFilter pred = liftM (filter pred)
    testFilter :: (Either Bool Integer) -> Bool
    testFilter (Left True) = True
    testFilter (Right x)   = even x
    testFilter _           = False
    showIt :: (Either Bool Integer) -> String
    showIt (Left True)  = "Left True"
    showIt (Left False) = "Left False"
    showIt (Right x)    = "Right x=" ++ (show x)
    test = do
        filtered <- liftFilter testFilter testCase
        return (fmap showIt filtered)
    runTest = do
        actions <- liftM (fmap putStrLn) test
        sequence_ actions
◀ Go back