Here is filter and its monadic cousin filterM:

filter  ::            (a ->   Bool) -> [a] ->   [a]
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

This is my attempt to understand the relevance of the differences between these two functions. Please leave a comment to let me know about anything I’ve misunderstood. :)

Filtering with Maybe

We can use the non-monadic filter to get a list of even numbers, or use fmap to apply this filter inside a monad (or any functor):

ghci> filter even [1..10]
[2,4,6,8,10]
ghci> fmap (filter even) (Just [1..10])
Just [2,4,6,8,10]

The filterM form gives us something fmap and filter can’t, and that’s allowing us to interact with a monadic context.

For example, say we want to filter out even numbers from an [Int], but we don’t want to return anything if any number is less than or equal to 0 (perhaps we want to call a function that only works with positive integers).

naturalEvens :: [Int] -> Maybe [Int]
naturalEvens = filterM (\i -> if i<=0 then Nothing else return (even i))
{-
ghci> naturalEvens [1..10]
Just [2,4,6,8,10]
ghci> naturalEvens [1,2,-5,4] 
Nothing
-}

filter takes a predicate (a -> Bool) which can only evaluate to True or False for each element – there is no way for it to interact with a monadic environment, even if it is mapped into one. Nor can fmap for that matter, as it works with functions (a -> b) and preserves the structure it is mapping over.

filterM doesn’t have this restriction due to its (a -> m Bool) argument, which in this case can produce Just True, Just False, or stop the computation by evaluating to Nothing.

Parser example

We can apply a similar filter function to a monadic parser.

-- parse will succeed with an `a` and the rest of the unparsed input,
-- or fail with Nothing.
data Parser a = P { parse :: String -> Maybe (String, a) }

If we have an instance of a Parser [Int] that parses comma-separated numbers, we can filter even numbers like in our previous example:

ghci> csv `parse` "no numbers"
Nothing
ghci> csv `parse` "1,2,3,4,5,6,7,8,9"
Just ("",[1,2,3,4,5,6,7,8,9])
ghci> fmap (filter even) csv `parse` "1,2,3,4,5,6,7,8,9"
Just ("",[2,4,6,8])

Now we want to filter even numbers from our parser, but we want to stop parsing if we get 0 or a negative number. We can use filterM to construct a new parser from our csv parser that does this:

naturalEvens :: [Int] -> Parser [Int]
naturalEvens = filterM $ \i ->
                  if i<=0 then failP else return (even i)
{-
ghci> (csv >>= naturalEvens) `parse` "1,2,3,4,5,6,7,8,9"
Just ("",[2,4,6,8])
ghci> (csv >>= naturalEvens) `parse` "1,2,-3,4"
Nothing
-}

State example

Another example from Tony Morris’s Haskell exercises is getting a distinct list of elements using the State monad with a Data.Set to keep track of which elements have been seen:

distinct :: Ord a => [a] -> [a]
distinct =
    flip evalState S.empty .
        filterM (\a -> state (\s -> (S.notMember a s, S.insert a s)))
        -- or: filterM (liftA2 (&&&) S.notMember S.insert)

ghci> distinct [1,2,3,34,4,23,3,2,3,22,2,4,5]
[1,2,3,34,4,23,22,5]

filterM ensures that the state (the contents of the Data.Set) is preserved as each element in the source list is traversed.

IO example

Say we want to filter a list of files paths to only include files that exist. This requires checking the file system, which requires a FilePath -> IO Bool function called doesFileExist:

validFiles :: [FilePath] -> IO [FilePath]
validFiles = filterM doesFileExist
{-
ghci> validFiles ["data.hs", "fileReader.hs", "non-existent"]
["data.hs","fileReader.hs"]
-}

Conclusion

What hadn’t really twigged for me previously is that filterM’s first argument (a -> m Bool) lets us do standard filtering like filter, but gives us the additional option to keep some monadic effect while filtering, such as canceling a computation with Nothing or by failing parsing, or updating some state. In contrast, mapping filter inside a monad does not give us this ability to interact with that effect¹.