我不明白爲什麼不能Haskell推斷這種類型

Question

我試圖用foldr實現filterM函數，但接收到一個我不明白爲什麼的錯誤。

我的實現（它只是爲了解，我知道我應該使用做記號...）：

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 

我不知道爲什麼鍵入一個不能推導出因爲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) 

但是，你在foldFn的定義，它說，m1必須是精確的相同m從上面使用f。您不希望foldFn的類型在任何Monad上工作，只有f正在使用的Monad。這是一個微妙的差異，一開始就很難找到。它也適用於這兩個簽名中的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-reducing filterM使list變量隱含，並刪除一些不必要的括號。