I can’t understand why Haskell cannot deduce this type

Question

I tried to implement the filterM function with foldr, but I get an error that I cannot understand why.

my implementation (this is just for understanding, I know that I should use the 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 = fx 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: fx In an equation for `m': m = fx 

I don’t understand why type a cannot be inferred since foldr is of type foldr :: (a -> b -> b) -> b -> [a] -> b

Thanks in advance, Alex

Answer 1

I believe what you had in mind

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

not xs at the end, so I will take that in the future.

The problem you are facing is that the type variables in the tick signature foldFn completely separate from the type variables in the signature of the filterM type. This is 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 = fx 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 should be the same as m from above. You do not want the foldFn type foldFn work on any Monad , only the Monad that uses f . This is a subtle difference, and difficult to determine first. This also applies to the difference between a and b in the two signatures. You can simply remove the type signature for foldFn , and GHC can correctly infer the type foldFn , but in cases where this does not work, you can use the ScopedTypeVariables extension. I would not recommend using it in this case, but there are times when it is 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 <- fx return (if b then x:l else l) 

And now m and a in both type signatures refer to the same type variables. I will also let hlint report some improvements that can be made to your code, for example, moving the return from if on the last line using the do notation for foldFn and eta-reduction filterM to make the list argument implicit, and also remove some unnecessary parentheses .