试图理解为什么这个函数在 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

我对此感到困惑，我认为这在某种程度上与函数的自由定义有关？请澄清这里的问题是什么。我学习的 link - https://en.wikibooks.org/wiki/Haskell/Lists_III

Answer 1

tl;博士

只是总是写显式类型签名，这样你就可以安全地避免遇到类似的奇怪问题。

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

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

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

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

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

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]

或者您可以为函数提供 list-specific 签名

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

这在 [1,2,3] 上同样有效，但不能接受 Map。

现在的问题是，为什么 GHC 不自己推断这些签名中的任何一个？好吧，如果它必须选择一个，它应该是更通用的 Foldable 版本，因为人们可能需要将它与其他容器一起使用并且不想继续重复 Foldable t => 量词。然而，这与另一个 Haskell 规则相矛盾，即 monomorphism restriction. Because your echoes implementation doesn't explicitly accept any parameters (it only does that point-freely), it is a constant applicative form，并且独立的 CAF 应该具有单态类型，除非明确指定为多态。因此，您运行的错误消息是：GHC 确实希望它是单态的，但它没有限制 what 具体 Foldable 容器选择的信息。

有四种解决方法：

正如您所注意到的，通过在范围内显式引入参数，echoes 不再是 CAF，因此 GHC 推断出多态类型：
```
echoes'' l = foldr (\x xs -> (replicate x x) ++ xs) [] l
```
```
> :t echoes''<br>echoes'' :: Foldable t => t Int -> [Int]
```

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

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

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

不鼓励如果你开启-XExtendedDefaultingRules扩展，GHC会自动选择[] 作为 CAF 的具体单态容器：
```
{-# LANGUAGE ExtendedDefaultRules #-}
echoes'''' = foldr (\x xs -> (replicate x x) ++ xs) []
```
```
> :t echoes''''<br>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<br>echoes :: Foldable t => t Int -> [Int]<br>> :t echoes'<br>echoes' :: [Int] -> [Int]

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

Trying to understanding why this function using foldr in Haskell isnt working

haskell

functional-programming

higher-order-functions

tl;博士