implementing a "findM" in Haskell?

Question

I am looking for a function that basically is like mapM on a list -- it performs a series of monadic actions taking every value in the list as a parameter -- and each monadic function returns m (Maybe b). However, I want it to stop after the first parameter that causes the function to return a Just value, not execute any more after that, and return that value.

Well, it'll probably be easier to just show the type signature:

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b)

where b is the first Just value. The Maybe in the result is from the finding (in case of an empty list, etc.), and has nothing to do with the Maybe returned by the Monadic function.

I can't seem to implement this with a straightforward application of library functions. I could use

findM f xs = fmap (fmap fromJust . find isJust) $ mapM f xs

which will work, but I tested this and it seems that all of the monadic actions are executed before calling find, so I can't rely on laziness here.

ghci> findM (\x -> print x >> return (Just x)) [1,2,3]
1
2
3
-- returning IO (Just 1)

What is the best way to implement this function that won't execute the monadic actions after the first "just" return? Something that would do:

ghci> findM (\x -> print x >> return (Just x)) [1,2,3]
1
-- returning IO (Just 1)

or even, ideally,

ghci> findM (\x -> print x >> return (Just x)) [1..]
1
-- returning IO (Just 1)

Hopefully there is an answer that doesn't use explicit recursion, and are compositions of library functions if possible? Or maybe even a point-free one?

Answer 1

One simple point-free solution is using the MaybeT transformer. Whenever we see m (Maybe a) we can wrap it into MaybeT and we get all MonadPlus functions immediately. Since mplus for MaybeT does exactly we need - it runs the second given action only if the first one resulted in Nothing - msum does exactly what we need:

import Control.Monad
import Control.Monad.Trans.Maybe

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b)
findM f = runMaybeT . msum . map (MaybeT . f)

---

Update: In this case, we were lucky that there exists a monad transformer (MaybeT) whose mplus has just the semantic we need. But in a general case, it can be that it won't be possible to construct such a transformer. MonadPlus has some laws that must be satisfied with respect to other monadic operations. However, all is not lost, as we actually don't need a MonadPlus, all we need is a proper monoid to fold with.

So let's pretend we don't (can't) have MaybeT. Computing the first value of some sequence of operations is described by the First monoid. We just need to make a monadic variant that won't execute the right part, if the left part has a value:

newtype FirstM m a = FirstM { getFirstM :: m (Maybe a) }
instance (Monad m) => Monoid (FirstM m a) where
    mempty = FirstM $ return Nothing
    mappend (FirstM x) (FirstM y) = FirstM $ x >>= maybe y (return . Just)

This monoid exactly describes the process without any reference to lists or other structures. Now we just fold over the list using this monoid:

findM' :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b)
findM' f = getFirstM . mconcat . map (FirstM . f)

Moreover, it allows us to create a more generic (and even shorter) function using Data.Foldable:

findM'' :: (Monad m, Foldable f)
        => (a -> m (Maybe b)) -> f a -> m (Maybe b)
findM'' f = getFirstM . foldMap (FirstM . f)

Answer 2

I like Cirdec's answer if you don't mind recursion, but I think the equivalent fold based answer is quite pretty.

findM f = foldr test (return Nothing) 
    where test x m = do
              curr <- f x 
              case curr of
                  Just _  -> return curr
                  Nothing -> m

A nice little test of how well you understand folds.

Answer 3

This should do it:

findM _ [] = return Nothing
findM filter (x:xs) =
    do
        match <- filter x
        case match of
             Nothing -> findM filter xs
             _ -> return match

If you really want to do it points free (added as an edit)

The following would find something in a list using an Alternative functor, using a fold as in jozefg's answer

findA :: (Alternative f) => (a -> f b) -> [a] -> f b
findA = flip foldr empty . ((<|>) .)

I don't thing we can make (Monad m) => m . Maybe an instance of Alternative, but we could pretend there's an existing function:

-- Left biased choice
(<||>) :: (Monad m) => m (Maybe a) -> m (Maybe a) -> m (Maybe a)
(<||>) left right = left >>= fromMaybe right . fmap (return . Just)
-- Or its hideous points-free version
(<||>) = flip ((.) . (>>=)) (flip ((.) . ($) . fromMaybe) (fmap (return . Just)))

Then we can define findM in the same vein as findA

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b)
findM = flip foldr (return Nothing) . ((<||>) .)