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 effect1.
I think this limitation can also be a big advantage. Using
fmap
means we know we aren’t going to interacting with a monadic context, so we can safely transform anm a
without being concerned about ill effects.↩