Tôi không thể hiểu tại sao Haskell không thể suy ra loại này

Question

Tôi đã cố gắng triển khai chức năng filterM bằng cách sử dụng foldr, nhưng nhận được lỗi mà tôi không thể hiểu tại sao.

thực hiện của tôi (Người ta chỉ cho sự hiểu biết, tôi biết tôi nên sử dụng làm ký hiệu ...):

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) 

Tôi Lấy lỗi sau

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 

Tôi không hiểu tại sao loại không thể được suy luận vì foldr có loại foldr :: (a -> b -> b) -> b -> [a] -> b

Cảm ơn trước, Alex

Answer 1

Tôi tin rằng bạn có nghĩa là

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

hơn xs ở cuối, vì vậy tôi sẽ giả định rằng trong tương lai.

Sự cố bạn gặp phải ở đây là các biến loại trong chữ ký loại foldFn hoàn toàn tách biệt với các biến loại trong chữ ký loại filterM. Nó thực sự tương đương với nói

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) 

Tuy nhiên, bạn sử dụng f trong định nghĩa của foldFn, mà nói rằng m1 phải là chính xác giống như các m từ trên cao. Bạn không muốn loại foldFn để hoạt động trên bất kỳ Monad nào, chỉ Monad mà f đang sử dụng. Đây là một sự khác biệt tinh tế và một khó khăn để phát hiện ngay từ đầu. Nó cũng áp dụng cho sự khác biệt giữa a và b trong hai chữ ký này. Những gì bạn có thể làm chỉ đơn giản là loại bỏ chữ ký loại cho foldFn và GHC có thể suy ra một cách chính xác loại foldFn, nhưng trong trường hợp điều này không hoạt động, bạn có thể sử dụng phần mở rộng ScopedTypeVariables. Tôi sẽ không khuyên bạn sử dụng nó trong trường hợp này, nhưng có những lúc nó thực sự hữu ích hoặc thậm chí cần thiết:

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

Và bây giờ là m và a trong cả hai loại chữ ký đề cập đến các biến cùng loại. Tôi cũng hãy hlint cho tôi biết một số cải tiến mà có thể được thực hiện cho mã của bạn, chẳng hạn như di chuyển return ra khỏi if tuyên bố trên dòng cuối cùng, sử dụng do ký hiệu cho foldFn và eta-giảm filterM để làm cho list tranh luận ngầm , cũng như loại bỏ một số dấu ngoặc đơn không cần thiết.