Foldr 递归模式中的 f [] = v 是什么意思？

Question

当对函数乘积使用 Foldr 递归模式时，我们得到：

product [] = 1
product (x:xs) = x * product xs

我的问题是，'product [] = 1' 是什么意思？例如，对于 sum 函数，我们有 sum[] = 0?这是对答案的某种限制吗？

提前谢谢你。

Answer 1

product [] 是基本情况。通过对函数的求值，很容易看出它存在的原因。

product [5, 4, 8]
5 * product [4, 8]
5 * 4 * product [8]
5 * 4 * 8 * product []
5 * 4 * 8 * 1
160

如果基本情况不存在，product [] 将无法评估任何结果。 1 是乘法的恒等式，就像 0 是加法的恒等式一样，即任何数乘以 1 总是那个数，就像 0 加任何数都是那个数。

Answer 2

为了x = product [x]成立，product [] = 1必然成立，因为根据你的定义，

 product [x] = product (x:[]) = x * product []

但从更广的角度来看（即考虑到 xs == xs ++ []），

product (xs ++ ys) = product xs * product ys    -- and so,

product (xs ++ []) = product xs * product []

product = foldr (*) 1 = getProduct . foldMap Product

并且根据 1986 年 Richard Bird 的 An Introduction to the Theory of Lists, reducing (folding) with an associative operation, like multiplication, is a homomorphism 列表（反之亦然），即

foldr (*) 1 (xs ++ ys)  =  foldr (*) 1 xs  *  foldr (*) 1 ys   -- and so,

foldr (*) 1 (xs ++ [])  =  foldr (*) 1 xs  *  foldr (*) 1 []

从数学上讲，(*)和1组成一个monoid。幺半群与 folding in Haskell:

密切相关

foldMap :: Monoid m => (a -> m) -> f a -> m

上面f是一个Foldable类型，其中lists([]) 是一个。所以这一切都是相连的。

What does f [] = v mean in the Foldr Recursion Pattern?