haskell - 我不明白为什么 Haskell 不能推断出这种类型

Question

我试图使用 foldr 实现 filterM 函数，但收到一个我不明白为什么的错误。

我的实现(只是为了理解，我知道我应该使用 do 符号......):

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)

我收到以下错误

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

我不明白为什么不能推导出类型 a，因为 foldr 的类型是 foldr :: (a -> b -> b) -> b -> [a] -> b
提前致谢，
亚历克斯

Answer 1

我相信你的意思

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

而不是 xs最后，所以我会假设前进。

您在这里遇到的问题是 foldFn 中的类型变量的类型签名与 filterM 中的类型变量完全分开的类型签名。真的相当于说

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)

但是，您使用 f在 foldFn的定义中，这表示 m1必须与 m 完全相同从上面。你不想要 foldFn 的类型处理任何 Monad ，只有 Monad那个 f正在使用。这是一个微妙的差异，一开始很难发现。它也适用于 a 之间的差异和 b在这两个签名中。您可以做的只是删除 foldFn 的类型签名并且 GHC 可以正确推断 foldFn 的类型，但如果这不起作用，您可以使用 ScopedTypeVariables延期。我不建议在这种情况下使用它，但有时它真的很有用甚至是必要的:

{-# 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)

而现在 m和 a在两个类型签名中都引用了相同的类型变量。我也让 hlint 告诉我一些可以对您的代码进行的改进，例如移动 return出了 if最后一行的语句，使用 do foldFn 的符号, 和 eta 减少 filterM制作 list参数隐式，以及删除一些不必要的括号。