A handy generalized filter

For quite a while, I’ve been using a handy operation for filtering functional events:

justE :: Event (Maybe a) -> Event a

The idea of justE is to drop the Nothing-valued occurrences and strip off the Just constructors from the remaining occurrences. Recently I finally noticed the similarity with a standard function (in Data.Maybe):

catMaybes :: [Maybe a] -> [a]

I asked on #haskell about a common generalization, and oerjan offered the following:

joinMaybes :: MonadPlus m => m (Maybe a) -> m a
joinMaybes = (>>= maybe mzero return)

I like this name and definition very much, including the use of mzero and return for empty and singleton monadic values, respectively. I particularly like how it works out for lists and events. Each element is passed into maybe mzero return, so that a Nothing becomes empty (mzero), while a Just x becomes a singleton (return x).

I also like how joinMaybes specializes easily into traditional, predicate-based filtering, generalizing the standard filter function on lists:

filterMP :: MonadPlus m => (a -> Bool) -> m a -> m a
filterMP p m = joinMaybes (liftM f m)
 where
   f a | p a       = Just a
       | otherwise = Nothing

So it’s easy to define filterMP in terms of joinMaybes (and hence filter in terms of catMaybes). What about the reverse? Here’s one go at it:

filterMP' :: MonadPlus m => (a -> Bool) -> m a -> m a
filterMP' p = (>>= f)
 where
   f a | p a       = return a
       | otherwise = mzero
 
joinMaybes' :: MonadPlus m => m (Maybe a) -> m a
joinMaybes' = liftM fromJust . filterMP' isJust

Comparable simplicity, but I don’t like the isJust and fromJust. Not only is there some redundant checking, but the fromJust function is partial, and so this definition is not so obviously total to an automated checker like Catch.


Edit 2008-02-08: added a “Continue reading …” token, to keep my blog’s front page uncluttered.

4 Comments

  1. Neil Mitchell:

    Conal, Catch would happily accept the above definition as total and spot that the filter guarantees the Just property – its trivial for Catch. As an added bonus, Supero would optimise out the redundant Just matches, giving you something maximally efficient.

    The moral of the story is just code simple, and I’ll come round later and take care of it!

  2. Neil Mitchell:

    I’ve also written some more about it at http://neilmitchell.blogspot.com/2008/01/safety-and-optimisation-joinmaybes.html

  3. conal:

    That’s terrific, Neil. Good stuff!

  4. Conal Elliott » Blog Archive » Invasion of the composable Mutant-Bots:

    [...] About « A handy generalized filter [...]

Leave a comment