I can't understand why can't Haskell deduce this type

Question

I was trying to implement the filterM function using foldr, but receiving an error which I can't understand why.

my implementation (It is just for understanding, I know i should use do notation...):

filterM :: (Monad m) => (a -> (m Bool)) -> [a] -> m [a]
filterM f list = foldr foldFn (return []) list
    where 
        foldFn :: (Monad m) => a -> m [a] -> m [a]
        foldFn x acc = let 
            m = f x
            in acc >>= 
                \l -> m >>= 
                    \b -> (if b == True then return (x:l) else return l)

I Get the following error

Could not deduce (a ~ a1)
from the context (Monad m)
  bound by the type signature for
             filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
  at wadler.hs:124:12-55
or from (Monad m1)
  bound by the type signature for
             ff :: Monad m1 => a1 -> m1 [a1] -> m1 [a1]
  at wadler.hs:127:23-54
  `a' is a rigid type variable bound by
      the type signature for
        filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
      at wadler.hs:124:12
  `a1' is a rigid type variable bound by
       the type signature for ff :: Monad m1 => a1 -> m1 [a1] -> m1 [a1]
       at wadler.hs:127:23
In the first argument of `f', namely `x'
In the expression: f x
In an equation for `m': m = f x

I don't get why type a can't be deduced since foldr has type foldr :: (a -> b -> b) -> b -> [a] -> b

Thanks in advance, Alex

Answer 1

I believe that you meant

filterM f list = foldr foldFn (return []) list

rather than xs at the end, so I'll assume that going forward.

The problem you're experiencing here is that the type variables in foldFn's type signature is completely separate from type variables in filterM's type signature. It's really equivalent to saying

filterM :: (Monad m) => (a -> (m Bool)) -> [a] -> m [a]
filterM f list = foldr foldFn (return []) list
    where 
        foldFn :: (Monad m1) => a1 -> m1 [a1] -> m1 [a1]
        foldFn x acc = let 
            m = f x
            in acc >>= 
                \l -> m >>= 
                    \b -> (if b == True then return (x:l) else return l)

But, you use f in the definition of foldFn, which says that m1 has to be the exact same as the m from above. You don't want the type of foldFn to work on any Monad, only the Monad that f is using. This is a subtle difference and a difficult one to spot at first. It also applies to the difference between a and b in these two signatures. What you can do is simply remove the type signature for foldFn and GHC can correctly infer the type of foldFn, but in cases where this doesn't work, you can use the ScopedTypeVariables extension. I would not recommend using it in this case, but there are times when it's really useful or even necessary:

{-# LANGUAGE ScopedTypeVariables #-}

filterM :: forall m a. (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM f = foldr foldFn (return [])
    where
        foldFn :: (Monad m) => a -> m [a] -> m [a]
        foldFn x acc = do
            l <- acc
            b <- f x
            return (if b then x:l else l)

And now the m and a in both type signatures refer to the same type variables. I've also let hlint tell me some improvements that could be made to your code, such as moving the return out of the if statement on the last line, using do notation for foldFn, and eta-reducing filterM to make the list argument implicit, as well as removing some unnecessary parentheses.