1

我正在编写允许对范围进行一些函数编程操作的库。范围是 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

4

1 回答 1

2

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

传统上，折叠被定义为在（初始，第一个），然后（旧值，下一个）上递归调用所述二进制函数，直到你用完调用它的东西。

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

因此，减法和除法的“文件夹”要么是“逆的总和”，要么是“逆的乘积”（即 fold(r) = 1/fold(r) 和 fold(r) = -fold(r)，这似乎很无聊），或者它们是根本不同的东西，不适用于空容器。

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

通过“不工作”，他们可以抛出异常，或者他们可以返回类似 a 的东西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 = xallx的元素。有一个对 all的元素e，即 0）。x-e = xx

取幂也是如此（它的右手身份为1，但没有左手身份）。

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

于 2012-12-12T19:31:40.190 回答