haskell - 带有 4 个参数的foldr？

Question

我很难理解为什么这段代码取自 haskell.org exercise page类型检查(并用作列表反转函数):

myReverse :: [a] -> [a]
myReverse xs = foldr (\x fId empty -> fId (x : empty)) id xs []

我的第一个困惑点是，foldr 接受 3 个参数，而不是 4 个:

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

所以我猜测 myReverse 相当于:

myReverse xs = foldr ((\x fId empty -> fId (x : empty)) id) xs []

但是这也不应该起作用，因为在 lambda 中，x 是一个列表元素而不是函数......

Answer 1

这样想吧。每个函数只接受一个参数。它可能返回另一个函数(接受一个参数)。看起来像多参数调用的东西

f a b c

实际上被解析为

((f a) b) c

即单参数函数应用程序链。函数类型

f :: a -> b -> c -> d

可以分解为

f :: a -> (b -> (c -> d))

即一个函数返回一个函数返回一个函数。我们通常将其视为三个参数的函数。但它可以接受三个以上吗？是的，如果 d 恰好是另一种函数类型。

这正是您的 fold 示例中发生的情况。作为第一个参数传递给 foldr 的函数接受三个参数，这与接受两个参数并返回另一个函数完全相同。现在 foldr 的(简化)类型是

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

但是如果你看一下它的第一个参数，你会发现它是三个参数的函数。正如我们所看到的，这与添加两个参数并返回一个函数的函数完全相同。所以 b 恰好是一个函数类型。由于 b 也是应用于三个参数时 foldr 的返回 tuoe

foldr (\x fId empty -> fId (x : empty)) id

它是一个函数，现在可以应用于另一个参数

(foldr (\x fId empty -> fId (x : empty)) id xs) []

我让你弄清楚 b 实际上是什么。