这个折叠实现中的错误

Question

在这个关于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

在递归模式之间z和f内部似乎存在反转:否则如何z f xs匹配(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
...

但是,在讲座后不久,您可以找到以下声明:

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

没有.一旦你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))