haskell - foldr 函数的 "accumulating parameter"的标识

Question

文件夹 函数:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr func acc []      = acc
foldr func acc (x:xs)  = func x (foldr func acc xs)

捕捉这样的模式(左侧)
并使它们更简单(右侧)

sum :: [Integer] -> Integer       |  sum :: [Integer] -> Integer
sum [] = 0                        |  sum [] = 0
sum (x:xs) = x + sum xs           |  sum (x:xs) = foldr (+) 0 xs
                                  |
product :: [Integer] -> Integer   |  product :: [Integer] -> Integer
product [] = 0                    |  product [] = 0
product (x:xs) = x * product xs   |  product (x:xs) = foldr (*) 1 xs
                                  |
concat :: [[a]] -> [a]            |  concat :: [[a]] -> [a]
concat [] = []                    |  concat [] = []
concat (x:xs) = x ++ concat xs    |  concat (x:xs) = foldr (++) [] xs
----------------------------------------------------------------------
       not using folds            |           using folds 

我注意到的一件事是 acc 参数，作为折叠的输入提供，
似乎正是该功能的中性元素/身份元素。

In Mathematics the neutral element of the addition operation + is 0
because n + 0 = n, n ∈ ℝ

它不会改变任何东西，换句话说:
将此中性元素作为加法函数的输入提供，被加数等于总和。
(+) summand 0 = summand 或 summand + 0 = summand
乘法也是如此，因子和恒等式的乘积等于因子 itelf:
(*) factor 1 = factor
那么这只是巧合还是背后有更大的事情？

Answer 1

你说得对。我们经常希望向 foldr 传递一个类似“身份”的元素，以便“起点”根本不会影响结果。事实上，这是在 Haskell 中用 Monoid 类型类编码的。 monoid 是具有身份的关联二元运算。你提供的例子都是幺半群的例子，它们都存在于Haskell中。

任何 + 上的 Num 都被编码为 Sum newtype 上的幺半群。

任何 * 上的 Num 都被编码为 Product newtype 上的幺半群。

任何列表上的 ++ 都被编码为 [a] 上的幺半群。

事实上，我们可以更进一步。折叠幺半群是一种常见的做法，我们可以使用 fold (或 foldMap ，如果您需要消除歧义)自动完成。例如，

import Data.Foldable
import Data.Monoid

sum :: Num a => [a] -> a
sum = getSum . foldMap Sum

product :: Num a => [a] -> a
product = getProduct . foldMap Product

concat :: [[a]] -> [a]
concat = fold

如果您查看 Foldable 的源代码，您会发现 fold 和 foldMap 实际上是根据幺半群上的 foldr 定义的，因此这与您刚刚描述的完全相同。

您可以在 Hackage 上找到(内置) Monoid 实例的完整列表，但还有一些您可能会感兴趣的:

bool 值上的 || 是具有 Any newtype 的幺半群。

bool 值上的 && 是具有 All newtype 的幺半群。

函数组合是具有 Endo newtype(“内同态”的缩写)的幺半群

作为练习，您可以考虑尝试查明每个操作的身份。