Associativity of fold-expressions

Question

N4191 proposed fold-expressions to C++. The definition there was that

(args + ...)

is a left-fold (i.e. (((a0 + a1) + a2) + ...), and that

(... + args)

is a right-fold (i.e. (... + (a8 + (a9 + a10))). However, the revised paper N4295 reversed the definitions of left and right unary folds.

Question: what is the rationale? It seems more intuitive (at least when you are used to left-to-right alphabets) to evaluate (args + ...) from left-to-right.

I don't know their rationale, but to me `(... + args)` looks like a sub-expression of the left fold `(((... + a8) + a9) + a10) `. And similarly `(args + ...)` looks like a sub expression of right fold `(a0 + (a1 + (a2 ...)))`. — eerorika, Feb 02 '16 at 20:55
@user2079303 left-associativity of `a + b + c` is commonly defined as (a + b) + c, you are using the opposite — TemplateRex, Feb 02 '16 at 21:18
@TemplateRex I don't think that I'm using an opposite definition. The expressions in my comment fit perfectly to that definition. My expressions are sub-expressions of equivalent full-expressions that your sub-expressions are part of (sorry if that doesn't make any sense). I just show the opposite end than you do. — eerorika, Feb 02 '16 at 21:27
Also, think about consistency with binary folds. You really want `(std::cout << ... << args)` to work... — T.C., Feb 02 '16 at 23:40
[Richard's answer](https://groups.google.com/a/isocpp.org/d/msg/std-discussion/Sxbm2CEpMv4/CbfJtKGLEAkJ). — cpplearner, Feb 03 '16 at 12:51

score 10 · Accepted Answer · answered Feb 03 '16 at 15:31

From the comment by @cpplearner, here's some archeology from std-discussion

On Wed, Feb 4, 2015 at 1:30 AM, @T.C. wrote:

In N4295, which was actually voted into the standard,

(... op e) is a unary left fold;

(e op ...) is a unary right fold;

In N4191, however,

(e op ...) is called a left fold.

(... op e) is called a right fold.

Why the 180-degree turn?

And the answer by @RichardSmith

The form in the original paper was simply a typo. Here are some reasons why the definition that was voted into the standard is the correct one:

In the standard's formulation, (e op ...) has subexpressions of the form (e_i op <stuff>). It does not have subexpressions of the form (<stuff> op e_i). This is consistent with all other pack expansions, where the expansion comprises repeated instances of the pattern.

(e op ... op eN), where eN is a non-pack, must have eN as the innermost operand in order to be useful -- that is, it must be (e1 op (e2 op (e3 op (... op eN)...))), not (...(((e1 op e2) op e3) op ...) op eN) -- and vice versa for (e0 op ... op e). This allows, for instance, (string() + ... + things) and (std::cout << ... << things) to work. For consistency, (e op ...) must also be (e1 op (e2 op (...))).

eerorika · Answer 2 · 2016-02-02T21:59:30.650

I can't speak for the proposal, but the new, swapped definitions seem natural to me. My rationale for that is that (... + args) is a sub-expression of a left fold, and (args + ...) is a sub expression of a right fold. In fact, the former is the final segment, and the latter is the initial segment of the expression (I may not be using the correct terminology).

Here is how I would illustrate the expansion of the fold from the syntax:

Left fold

                     (... + args)
             (... + args) + a999)
     (... + args) + a998) + a999)

((...((a0 + a1) + a2)...) + a999)

Right fold

(args + ...)
(a0 + (args + ...)
(a0 + (a1 + (args + ...)

(a0 + (...(a997 + (a998 + a999))...))

Associativity of fold-expressions

2 Answers2

Linked