haskell - 试图理解为什么在 Haskell 中使用 foldr 的这个函数不起作用

Question

所以我是 Haskell 的新手，并使用 WikiBooks 学习它。在高阶函数章节中，使用了以下示例。

echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

所以我尝试运行它，但它给了我如下错误:

 * Ambiguous type variable `t0' arising from a use of `foldr'
  prevents the constraint `(Foldable t0)' from being solved.
  Relevant bindings include
    echoes :: t0 Int -> [Int] (bound at HavingFun.hs:107:1)
  Probable fix: use a type annotation to specify what `t0' should be.
  These potential instances exist:
    instance Foldable (Either a) -- Defined in `Data.Foldable'
    instance Foldable Maybe -- Defined in `Data.Foldable'
    instance Foldable ((,) a) -- Defined in `Data.Foldable'
    ...plus one other
    ...plus 29 instances involving out-of-scope types
    (use -fprint-potential-instances to see them all)
* In the expression: foldr (\ x xs -> (replicate x x) ++ xs) []
  In an equation for `echoes':
      echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

然后，如果我按如下方式编写它，它就可以工作。

echoes lis = foldr (\ x xs -> (replicate x x) ++ xs) [] lis

我对此感到困惑，我认为这是某种相关的函数的无点定义？
请澄清这里有什么问题。
我正在学习的链接 - https://en.wikibooks.org/wiki/Haskell/Lists_III

Answer 1

tl;博士
只是 总是写明确的类型签名 ，那么您就可以安全(r)摆脱这样的奇怪问题了。

这曾经有效但现在无效的原因是 foldr以前有签名

foldr :: (a -> b -> b) -> b -> [a] -> b

这是 WikiBooks 所假设的，但在较新的 GHC 中，它实际上具有更严格的通用签名

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

旧版本是一个特例，只需选择 t ~ [] .他们更改它的原因是您还可以折叠其他容器，例如数组或 map 。实际上，在您的代码中

echoes = foldr (\ x xs -> (replicate x x) ++ xs) []

也没有什么要求输入容器是一个列表，所以它实际上可以很好地与签名一起工作

echoes :: Foldable t => t Int -> [Int]

...其中，再次， [Int] -> [Int]是一种特殊情况，因此该函数可以用作

> echoes [1,2,3]
[1,2,2,3,3,3]

但也作为

> echoes $ Data.Map.fromList [('a',2), ('c',5), ('b',1)]
[2,2,1,5,5,5,5,5]

或者您可以为该函数提供特定于列表的签名

echoes' :: [Int] -> [Int]
echoes' = foldr (\x xs -> (replicate x x) ++ xs) []

这在 [1,2,3] 上同样有效但不能接受 Map .
现在的问题是，为什么 GHC 不能自己推断出这些签名中的任何一个？好吧，如果非要选一个的话，应该是比较通用的 Foldable版本，因为人们可能需要将它与其他容器一起使用，并且不想继续重复 Foldable t =>量词。然而，这与另一个 Haskell 规则相矛盾， monomorphism restriction .因为您的 echoes实现不明确接受任何参数(它只是自由地这样做)，它是 constant applicative form ，并且独立的 CAF 应该具有单态类型，除非明确指定为多态。因此，您遇到的错误消息:GHC 确实希望它是单态的，但它没有限制具体 Foldable 的信息。容器来挑选。
有四种方法可以解决这个问题:

正如您所注意到的，通过将参数显式引入范围，echoes不再是 CAF，因此 GHC 推断出多态类型:

echoes'' l = foldr (\x xs -> (replicate x x) ++ xs) [] l

> :t echoes''
echoes'' :: Foldable t => t Int -> [Int]

通过禁用单态限制，GHC 将不再关心它是否是 CAF，而只是给它更通用的类型，不管:

{-# LANGUAGE NoMonomorphismRestriction #-}
echoes''' = foldr (\x xs -> (replicate x x) ++ xs) []

> :t echoes'''
echoes''' :: Foldable t => t Int -> [Int]

气馁如果您打开 -XExtendedDefaultingRules扩展名，GHC会自动选择[]作为 CAF 的具体单态容器:

{-# LANGUAGE ExtendedDefaultRules #-}
echoes'''' = foldr (\x xs -> (replicate x x) ++ xs) []

> :t echoes''''
echoes'''' :: [Int] -> [Int]

GHCi有-XExtendedDefaultingRules默认情况下启用，因此如果您只是在 GHCi 提示符中声明该函数，也会发生这种情况。

强烈推荐如果您明确指定签名，则您和 GHC 都确切地知道其意图并相应地采取行动，而无需任何特殊的 GHC 扩展。

echoes :: Foldable t => t Int -> [Int]
echoes = foldr (\x xs -> (replicate x x) ++ xs) []

echoes' :: [Int] -> [Int]
echoes' = foldr (\x xs -> (replicate x x) ++ xs) []

> :t echoes
echoes :: Foldable t => t Int -> [Int]
> :t echoes'
echoes' :: [Int] -> [Int]