此折叠实现中的错误

Question

在this lecture关于Haskell的编程中，有一个fold实现，定义如下：

fold :: (a -> b -> b) -> b  -> [a] -> b
fold f z []     = z
fold f z (x:xs) = f x (fold z f xs)

想法是用它来定义总和、乘积等...

sum''     = fold (+) 0
product'' = fold (*) 1
length''  = fold addOne 0
 where addOne _ s = 1 + s

在递归模式中z和f之间似乎有一个反转：否则，z f xs如何匹配(a -> b -> b) -> b -> [a]？

在我看来，递归模式应该是

fold f z (x:xs) = f x (fold f z xs)

然而，在讲座后不久，您可以找到以下语句：

fold f z [a,b,c] = a `f` (b `f` (c `f` z))

这强化了所谓的错误，所以我想一定是我的脑袋出了问题！

不应该更像下面这样吗？

fold f z [a,b,c] = `f` a (`f` b (`f` c z))

我是不是漏掉了一点，还是在讲课中犯了双重错误？

Answer 1

代码fold f z (x:xs) = f x (fold z f xs)确实应该是fold f z (x:xs) = f x (fold f z xs)。

虽然第二部分是正确的，因为（注意反引号）

f x y == x `f` y

我们有

a `f` (b `f` (c `f` z)) == f a (f b (f c z)))

Answer 2

There seems to be an inversion between z and f inside the recursion pattern: otherwise how could z f xs match (a -> b -> b) -> b -> [a]?

你是对的，类型不一致，如果你尝试按给定的方式定义 fold，GHC 会很快通知你：

Couldn't match expected type ‘a -> b -> b’ with actual type ‘b’
  ‘b’ is a rigid type variable bound by
      the type signature for fold :: (a -> b -> b) -> b -> [a] -> b
      at test.hs:1:9
...

However, shortly after in the lecture, you can find the following statement:
fold f z [a,b,c] = a `f` (b `f` (c `f` z))
This reinforces the so-called mistake, so I guess there must be a mistake in my head instead!

Shouldn't it be more like the following ?
fold f z [a,b,c] = `f` a (`f` b (`f` c z))

没有。一旦你正确地定义了 fold，这个定义的展开就是正确的。作者只是简单地使用反引号将函数 f 用作中缀运算符：

fold f z [a,b,c] = a `f` (b `f` (c `f` z))

相当于

fold f z [a,b,c] = f a (f b (f c z))

但如果您将 f 视为二元函数（例如 (+)），则可能更具可读性；比较

fold (+) 0 [1,2,3] = 1 + (2 + (3 + 0))

可读性较差

fold (+) 0 [1,2,3] = (+) 1 ((+) 2 ((+) 3 0))

此折叠实现中的错误

Mistake in this fold implementation

recursion

haskell

pattern-matching