haskell - 此折叠实现中的错误

Question

在 this lecture关于 Haskell 编程，有一个折叠实现，定义如下:

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

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