fold 如何对空列表起作用？

Question

当我们折叠一个包含一个或多个元素的列表时，如下所示：

foldr (+) 0 [1,2,3]

We get:

foldr (+) 0 (1 : 2 : 3 : [])

foldr (+) 1 + (2 +(3 + 0)) // 6

现在当列表为空时：

 foldr (+) 0 []

Result: foldr (+) 0 ([])

由于 (+) 是二元运算符，它需要两个参数才能完成，但这里我们以 (+) 0 结尾。它如何导致 0 而不是抛出部分应用函数的错误。

Answer 1

简答：你得到初始值z.

如果您给 foldl 或 foldr 一个空列表，那么它 return 是初始值。 foldr :: (a -> b -> b) -> b -> t a -> b 工作方式如下：

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

因此，由于没有 x1、...、xn 函数从未应用，z 被 returned。

我们还可以检查 source code:

foldr            :: (a -> b -> b) -> b -> [a] -> b
-- foldr _ z []     =  z
-- foldr f z (x:xs) =  f x (foldr f z xs)
{-# INLINE [0] foldr #-}
-- Inline only in the final stage, after the foldr/cons rule has had a chance
-- Also note that we inline it when it has *two* parameters, which are the
-- ones we are keen about specialising!
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

因此，如果我们给 foldr 一个空列表，那么 go 将立即处理该空列表，并且 return z 初始值。

因此，更简洁的语法（并且效率稍低，如函数注释中所写）是：

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

请注意 - 根据 f 的实现 - 可以 foldr 在无限列表上：如果在某个时候 f 只查看初始值，然后return是一个值，那么递归部分可以去掉。

fold 如何对空列表起作用？

How does fold works for empty list?

haskell

fold