How can a variadic template be used to generate a left-associative expression (aka left fold) in c++11?

Question

I would like to use a c++ template to aggregate (fold) multiple arguments using a binary operation.

Such a template could be used as follows:

fold<add>(100,10,5) expands to add(add(100, 10), 5)

The particular expansion shown above is the "left fold". The expansion add(100, add(10, 5)) is the "right fold". Assuming that the add function performs simple integer addition, both right and left folds produce the same result, 115.

But consider a function div that performs integer division (div(a,b)=a/b). In this case, associativity matters and the left and right folds produce different results:

fold_left<div>(100,10,5)  --> div(div(100, 10), 5) --> div(10, 5) -->  2
fold_right<div>(100,10,5) --> div(100, div(10, 5)) --> div(100, 2) --> 50

It is straightforward to use a variadic template to produce the right-associative version (fold_right), but I have not been able to figure out how to produce the left-associative version (fold_left). The attempted implementation of fold_left below results in a compiler error:

#include <iostream>

template <typename T> using binary_op = T(*)(const T& a, const T& b);

// The terminal (single-argument) cases of the variadic functions defined later. 
template<typename T, binary_op<T> Operation> inline T fold_right(const T& t) { return t; }
template<typename T, binary_op<T> Operation> inline T fold_left(const T& t) { return t; }

// Combines arguments using right-associative operation
// i.e. fold_right<T,op>(A,B,C) --> op(A, op(B,C))
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_right(const T& t, Rest... rest) {
    return Operation(t, fold_right<T, Operation>(rest...));
}

// Combines arguments using left-associative operation
// i.e. fold_left<T,op>(A,B,C) --> op(op(A,B), C)
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_left(Rest... rest, const T& t) {
    return Operation(fold_left<T, Operation>(rest...), t);
}

inline int add(const int& a, const int& b) { return a+b; }
inline int div(const int& a, const int& b) { return a/b; }

int main() {
    std::cout << fold_right<int,div>(100,10,5) //  (100 / (10 / 5))  = 50
              << "\n"
              << fold_left<int,div>(100,10,5)  //  Compiler error!
              << std::endl;
    return 0;
}

How can variadic templates be used (in c++11) to correcty implement fold_left?

I think it essentially comes down to being able to "pop" the last argument off of a parameter pack, which I attempted to do in the left_fold template above, but as I said, this resulted in a compiler error.

Note: I have used simple arithmetic operations and integers as an example in this question, but the answer(s) should be generic enough to handle aggregation of objects using an arbitrary function (assuming it returns the same type of object as its arguments).

Note 2: For those familiar with c++17, fold expressions can be used to produce both left and right folds with binary operators. But these are not available in c++11.

As a related question: The above templates require the type T to be explicitly specified, as in fold_right<int,div>(...). Is there some way to formulate the template so that only the operation is required, e.g. fold_right<div>(...). I would think the type T could be inferred, but I don't see a way to order the template arguments to put the binary_op<> first.

Thanks!

Answer 1

Parameter packs on the left are problematic. Better reimplement it as a parameter pack on the right:

template<typename T, binary_op<T> Operation> 
inline T fold_left(const T& t) { return t; }

template<typename T, binary_op<T> Operation, typename ... Rest>
inline T fold_left(const T& a, const T& b, Rest... rest) {
    return fold_left<T, Operation>(Operation(a,b), rest...);
}