c++ - 对空范围进行折叠操作的结果

Question

我正在写 library它允许对范围进行一些函数编程操作。范围是 STL 容器的概括。我的问题是空范围折叠的结果应该是什么？

auto r  = range(4);    // lazy numeric range {0,1,2,3}
auto r0 = range(0);    // empty range {}
vector<string> vs  {"a", "bb"};
vector<string> vs0 {};

// this is obvious and implemented part    

cout <<  (r  || add);  // 6,  || - folding op
cout <<  (r0 || add);  // 0
cout <<  (vs || add);  // "abb"
cout <<  (vs0|| add);  // ""

cout <<  (r  || mul);  // 0
cout <<  (r0 || mul);  // 1

cout <<  (r  || max);  // 3

//  What result of these should be?

cout <<  (r0 || div);   // ???
cout <<  (r0 || sub);   // ???
cout <<  (r0 || max);   // -∞ ???
cout <<  (r0 || min);   // +∞ ???
cout <<  (r0 || ???);   // result of arbitrary op? 

编辑 - 回答

http://en.wikipedia.org/wiki/Identity_element

Answer 1

我假设您的“文件夹”是某个模板的实例，附加了一个二进制函数，可能还有一个初始值。

传统上，fold 被定义为递归调用所述二元函数(初始，第一个)，然后(旧值，下一个)，直到你用完所有东西来调用它。

没有这样的初始值可以让减法和除法按照您预期的方式工作(例如 fold({1,2}) 是 1/2)。

因此，减法和除法的“文件夹”要么是“逆的和”，要么是“逆的积”(即 fold(r) = 1/fold(r) 和 fold(r) = -fold(r) ，这看起来很无聊)，或者它们是根本不同的东西，不能在空容器上工作。

max 和 min 应该清楚地生成给定类型的最高值和最低值，或者是在空容器上没有意义的第二种类型的文件夹。

通过“不工作”，他们可以抛出一个异常，或者他们可以返回类似 boost::optional<T> 的东西-- 即，在空列表中，它们不返回任何内容。

您的文件夹类型可以采用一个函数来查找给定类型的初始值，该函数应解析为特征模板类或自由函数(类似于 std::begin )。

...

编辑:根据下面的评论，对答案进行改进。

这里真正的窍门是减法和除法没有左手恒等式，但有右手恒等式!

只有右手标识的操作应该表示为右手折叠，而只有左手标识的操作应该表示为左手折叠(又名 foldr 和 foldl)

即，在列表中表达折叠的自然方式 {a,b,c}有身份id二元运算 *op*是:

( (id *op* a) *op* b ) *op c

但对于没有左手身份的操作，这不起作用。

但是，如果你反转折叠惯用手，你会得到这个:

a *op* (b *op* (c *op* id))

只要你有一个正确的身份，它就可以工作。

这对 div 很重要和 sub -- div右侧标识为 1，并且 sub右侧恒等式为 0，但都没有左侧恒等式。 (没有元素 e 使得所有 e-x = x 为 x。有一个元素 e 使得所有 x-e = x 为 x，即 0)。

幂运算也是如此(它的右手标识为 1 ，但没有左手标识)。

这仍然不符合天真的期望 fold div应该做。它适用于长度为 2 的列表，但在长度为 3 的列表上会发生一些不直观的事情。但至少它在数学上是合理的。 :)