CODEWITHSUNDEEP
haskell
user181351
user181351

Reputation:

Is this function possible?

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

I cannot implement it by myself. I could use some pointers

find looks like:

find f as = listToMaybe $ filter f as

so I tried:

findM f as = filterM f as >>= listToMaybe

but it doesnt work.

Upvotes: 4

Views: 296

Answers (4)

jrmn
jrmn

Reputation: 431

For the 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 f m = m >>= filterM f >>= return . listToMaybe

or

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

for a point-free style.

Upvotes: 0

John L
John L

Reputation: 28097

Others have already demonstrated that this isn't possible, however with a further constraint you can get a very similar function.

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

Not every Monad has a Traversable instance, but if it does this will work.

Upvotes: 1

Ben Millwood
Ben Millwood

Reputation: 6991

Try

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

This version only uses the predicate as much as it has to, whereas the filterM version uses it on every element. So 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 "."

Upvotes: 7

Dietrich Epp
Dietrich Epp

Reputation: 213228

No. It is not possible. However, you can write a function with the signature:

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

The reason it is not possible is because in order to figure out if the Maybe has constructor Just x or Nothing, you have to get the value out of the monad. Which means that the Maybe must be inside the monad at the end, since it is not possible in general to extract a value from inside a monad. (That is the whole point of monads, after all.)

For example, given your signature to findM, you could write some obviously incorrect functions:

findM :: Monad m => (a -> m Bool) -> m [a] -> Maybe (m a)
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 function extractBool is obviously impossible, so findM cannot have that signature.

Here is an implementation of findM:

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

I am not sure of a simpler way to implement it -- this seems fairly clean, and it works on infinite lists.

Changing the signature from using an m [a] to using [a] makes it more useful and easier to use. You'll quickly figure out why, if you implement both interfaces.

Upvotes: 10

Related Questions