Implementing "findM" in Haskell?

Question

I am looking for a function that is basically similar to mapM in the list — it performs a series of monadic actions that take each 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, which causes the function to return a Just value, and not execute more after that and return that value.

Well, it will probably be easier to just show a signature like:

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

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

I cannot implement this with the simple use 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 monadic actions are performed before the find call, so I can not 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 does not perform monadic actions after the first "simple" return? Something to 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) 

I hope there is an answer that does not use explicit recursion and, if possible, is a composition of library functions? Or maybe even without dots ?

Answer 1

One simple MaybeT solution uses a MaybeT transformer. Whenever we see m (Maybe a) , we can MaybeT it in MaybeT and immediately get all the functions of MonadPlus . Since mplus for MaybeT does exactly what we need - it starts the second specified action only if the first result 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 are fortunate that there is a monad transformer ( MaybeT ), which mplus has only the semantics that we need. But in the general case, it may not be possible to build such a transformer. MonadPlus has some laws that must be followed regarding other monadic operations. However, all is not lost, since we really do not need MonadPlus , all we need is the correct monoid to add to.

So, let's pretend that we cannot (cannot) have MaybeT . The calculation of the first value of a certain sequence of operations is described by the monoid First . We just need to make a monadic version that will not perform the correct part if the left part matters:

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

This monoid accurately describes the process without reference to lists or other structures. Now we just add the list using this monoid:

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

In addition, this allows us to create a more general (and even shorter) function using Data.Foldable :

 findM'' :: (Monad m, Foldable f) => (a -> m (Maybe b)) -> fa -> 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 folding answer is pretty good.

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

A good 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 this, the dots are free (added as editing)

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

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

I can not do (Monad m) => m . Maybe (Monad m) => m . Maybe an Alternative instance, but we could pretend to be an existing function there:

 -- 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 way as findA

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

Answer 4

This can be pretty well expressed with MaybeT monad transformer and Data.Foldable .

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

And if you change the search function to create the MaybeT stack, it will become even nicer:

 findM' :: Monad m => (a -> MaybeT mb) -> [a] -> MaybeT mb findM' f = msum . map f 

Or without dots:

 findM' = (.) msum . map 

The original version can be done completely without dots, but it becomes quite unreadable:

 findM = (.) runMaybeT . (.) msum . map . (.) MaybeT