Filtering a list of monads

Question

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?

Answer 1

I am handling the lists using their monad instance instead of using filter method. It may be better to use the filter in real world situations. I'm also not trying to make my functions as small as possible

I assumed you want some arbitrary method to handle the Eithers. If you want to only filter the "right a" or get the left then you probably should use traversable. You also could use bimap to "fmap" left and right of Either simultaneously.

First a solution that works only with either:

filtermonads :: IO [(Either a b)] -> (a -> Bool) -> IO [(Either a b)]
filtermonads ioListEitherA cond = do
  listEitherA <- ioListEitherA
  return $ do
        eitherA <- listEitherA
        case eitherA of
          Left a -> if cond a then pure (Left a) else []
          Right b -> return (Right b)

Should be the same as the following:

filtermonads' :: IO [(Either a b)] -> (a -> Bool) -> IO [(Either a b)]
filtermonads' ioListEitherA cond = let
  f x = case x of
    Left a -> if cond a then pure (Left a) else []
    Right a -> pure (Right a)
  in
    fmap (join . fmap f) ioListEitherA

We have to manually open the Either as we require access to the information encapsulated inside it in order to know how to handle the list.

You could generalize this by instead separately providing a function (m2 a -> Bool) that tells how to extract the information from the monad.

eitherCond :: Either a b -> Bool
eitherCond eitherA = case eitherA of
          Left a -> False
          Right b -> True

filtermonads'' :: (Monad m) => m [a] -> (a -> Bool) -> m [a]
filtermonads'' m1listm2a cond = do
  listm2a <- m1listm2a
  return $ do
    m2a <- listm2a
    if cond m2a then pure m2a else []

You could also generalize the list to MonadPlus or MonadFail as you can think of filtering meaning you need a monad with a zero element. The monad library itself also has fail that is sometimes zero, but you should not use it as it is not a feature all plain monads have and as such the implementations are sometimes very arbitrary.

Plain filter might be better as only few structures implement the MonadPlus class. I should have used mfilter for this. MonadPlus also doesn't have that many structures that implement it. For example Map is not even a monad.

filtermonads''' :: (Monad m1, MonadPlus mp) => m1 (mp a) -> (a -> Bool) -> m1 (mp a)
filtermonads''' m1listm2a cond = do
  listm2a <- m1listm2a
  return $ do
    m2a <- listm2a
    if cond m2a then pure m2a else mzero

testData :: IO [Either Char Char]
testData = pure [Right 'a', Left 'a', Left 'c']

test1 = filtermonads testData (\x -> x=='a')
test2 = filtermonads' testData (\x -> x=='a')
test3 = filtermonads'' testData eitherCond
test4 = filtermonads''' testData eitherCond

justData ::IO (Maybe Char)
justData = pure (Just 'b')
readData :: Maybe (IO Char)
readData = Just (getChar) -- Notice that io mzero is error!
test5 = filtermonads''' justData (\x -> x=='a')
test6 = filtermonads''' readData (\x -> x=='a') 
main = case (test6) of
  Just a -> a >>= putStrLn . pure
  Nothing -> pure () 

Answer 2

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)

Answer 3

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