Is this function possible?

Question

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

I can not implement it myself. I could use some pointers

find looks like this:

 find f as = listToMaybe $ filter f as 

so i tried:

 findM f as = filterM f as >>= listToMaybe 

but it does not work.

Answer 1

No. It's impossible. However, you can write a function with a signature:

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

The reason is impossible, because in order to find out if Maybe has a Just x or Nothing constructor, you must get the value from the monad. This means that Maybe should be inside the monad at the end, since it is generally impossible to extract the value from within the monad. (After all, these are all monads).

For example, if your signature matches findM , you can write some obviously incorrect functions:

 findM :: Monad m => (a -> m Bool) -> m [a] -> Maybe (ma) findM = magic anyM :: Monad m => (a -> m Bool) -> m [a] -> Bool anyM f = isJust . findM f extractBool :: Monad m => m Bool -> Bool extractBool = anyM id . liftM (:[]) 

The extractBool function is obviously not possible, so findM cannot have such a signature.

Here is the findM implementation:

 findM :: Monad m => (a -> m Bool) -> [a] -> m (Maybe a) findM _ [] = return Nothing findM f (x:xs) = do y <- fx if y then return (Just x) else findM f xs 

I'm not sure about a simpler way to implement it - it seems pretty clean and it works with infinite lists.

Changing the signature with m [a] to use [a] makes it more useful and easier to use. You will quickly understand why if you implement both interfaces.

Answer 2

Try

 findM :: Monad m => (a -> m Bool) -> [a] -> m (Maybe a) findM p = foldr step (return Nothing) where step xr = do b <- px if b then return (Just x) else r 

This version uses only the predicate as necessary, while the filterM version uses it for each element. For example:

 ghci> let findM' p xs = filterM p xs >>= return . listToMaybe ghci> let check x = putStrLn ("checking " ++ show x) >> doesDirectoryExist x ghci> findM check ["test1", ".", "test2"] checking "test1" checking "." Just "." ghci> findM' check ["test1", ".", "test2"] checking "test1" checking "." checking "test2" Just "." 

Answer 3

Others have already demonstrated that this is not possible, but with a further restriction you can get a very similar function.

 findM :: (Traversable m, Monad m) => (a -> m Bool) -> m [a] -> Maybe (ma) findM p xs = Data.Traverse.sequence $ dietrichsFindM p xs 

Not every Monad has an instance of Traversable, but if it does, it will work.

Answer 4

For signature

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

I suggest:

 import Control.Monad import Data.Maybe findM :: Monad m => (a -> m Bool) -> m [a] -> m (Maybe a) findM fm = m >>= filterM f >>= return . listToMaybe 

or

 findM :: Monad m => (a -> m Bool) -> m [a] -> m (Maybe a) findM = ((return . listToMaybe =<<) .) . (=<<) . filterM 

for dot style.