I agree that that would solve the symmetry problem, and it would allow the type of the items in the generated sequence to be different from the input sequence. However, the problem is much less severe for partial_sum, because in most cases, it is possible to add two items of the relevant type.

The concept of "torsors" seems relevant here: https://math.ucr.edu/home/baez//torsors.html

> We can express this in terms of torsors as follows: energy differences lie in the group of real numbers R, but energies themselves do not: they lie in an "R-torsor".

So in the date example, we have a set T of intervals like "three days" which we can add to members of the set D of datetimes to get new elements of D, which is the torsor of T:

    D + T : D

And we can subtract two D elements to get the T from one to the other:

    D - D : T

    d1 + (d2 - d1) = d2

    partial_sum : (D, T[n]) -> D[n+1]
    adjacent_difference : D[n+1] -> (D, T[n])

Now, we can try to define an interval addition operation:

    T + T : T

    t1 + t2 = ((d1 + t1) + t2) - d1

In such a case your chosen set of intervals might not contain an element that could correctly represent "+2 months" + "+7 days". With different choices of d1, you might get a sum of "+67 days", "+66 days", "+69 days", etc.

The STL prefix_sum can't handle that, because it needs T + T to be well-defined. But your more-generic version takes a starting D element, so it can handle it fine.

However, I think it's fairly unusual to use such unruly data types with these algorithms. Torsors are defined, normally, on groups, so addition on T is guaranteed to not just exist, but have an identity and an inverse for every element, and be associative. And in such cases the STL's T[n] -> T[n] prefix_sum is in some sense "just as generic", because you can freely transform between D[n] and T[n] by adding or subtracting a predetermined "epoch date" or "freezing point".

——*——

There are some lovely wildflowers here if you have the patience for rambling off the trail a bit! The associativity of group operations gives rise to an efficient parallel algorithm for partial_sum (prefix sum) closely related to the parallel sum algorithm that Stepanov says originally inspired his work on generic algorithms when he realized that it was applicable to any monoid.

Often parallel algorithms correspond closely with incremental algorithms; that O(lg N) sum algorithm applicable to general monoids corresponds closely with an O(lg N) incremental sum update algorithm applicable to general monoids, where you sift updates up a binary tree from the changed input to the root. But for abelian groups like integer addition, there's an O(1) update algorithm: subtract the old value from the new, and add that difference to the sum.

However, the O(lg N) version is applicable to other monoids, such as max and min, which yields efficient incremental algorithms for problems like morphological dilation and erosion, where prefix sums are not applicable.

T{} is now sort of that, but it didn't exist yet when adjacent_difference was written.

They could have added an init parameter if int() or double() isn't enough

I think that would fix the issue at the type level (up to a point; for unsigned types, the "correct" type for the result of a subtraction is underdetermined -- it could be any of {same type, larger signed type, same-size signed type} depending on the circumstances).

But I think the more serious niggle is the fact that that first element shows up in the output at all. OTOH, I suppose you could write a discard_first iterator adaptor that ignores the first write and increment and passes the rest through to the underlying output iterator.

Was vector<bool> from the original STL or is it a committee invention?

This is also known as "The Fundamental Theorem of Stream Calculus" in stream calculus. Using coinduction for an (infinite) stream sigma, eg

    sigma(0)      = head(sigma)
    sigma'        = tail(sigma)
    (a ++ sigma)' = sigma