What is the difference between these mondaic functions?

user_8548828 0
Viewed 79

So I have these two functions:

filterM _ [] = []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

and

filterM _ [] = return []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

Resulting in these results for the following input: filterM (\x -> [True,False]) [0..3]

[]

or

[[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3]]

Why does return impact the execution so much?

monads haskell
1 Answers

Let us look at a simple case where we call:

filterM (const [True, False]) [0]

We expect that this will return [[0], [0]]. If we take a look at the first implementation, we see that this will result in:

filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- filterM (const [True, False]) []
    return (if n then 0:ys else 0:[])

If we take the first implementation, the the filterM (const [True, False]) [] will result in []. So this means that it will look like:

-- first implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- []
    return (if n then 0:ys else 0:[])

Since for the instance Monad [], the >>= is implemented as:

instance Monad [] where
    return x = [x]
    xs >>= f = [y | x <- xs, y <- f x]

this thus means that if xs is empty, then the result will be emtpy as well.

In the second implementation, return [] will result in [[]], so a singleton list where the single element is an empty list. In that case, it thus looks like:

-- second implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- [[]]
    return (if n then 0:ys else 0:[])

This thus means that we enumerate over the list, and ys will take the value [], so it will result in a list [[0], [0]].

Normally the filter will however not prepend x in both cases, furthermore you probably want to yield x:ys and ys; not x:ys and x:xs. A correct implementation is thus:

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM _ [] = return []
filterM p (x:xs) = do
    n <- p x
    ys <- filterM p xs
    return (if n then x:ys else ys)
user_675790
Related