This recipe looks really complicated because we are nesting lambda expressions a lot. In order to understand how this works, let's first have a look at the inner workings of std::accumulate. This is how it will look like in a typical STL implementation:

template <typename T, typename F>
T accumulate(InputIterator first, InputIterator last, T init, F f)
{
    for (; first != last; ++first) {
        init = f(init, *first);
    }
    return init;
}

The function parameter, f, does the main work here, while the loop collects its results in the user provided init variable. In a usual example case, the iterator range may represent a vector of numbers, such as 0, 1, 2, 3, 4, and the init value is 0. The f function is then just a binary function that might calculate the sum of two items using the + operator.

In this example case, the loop just sums up all the items into the init variable, such as in init = (((0 + 1) + 2) + 3) + 4. Writing it down like this makes obvious that std::accumulate is just a general folding function. Folding a range means applying a binary operation to an accumulator variable and stepwise every item contained in the range (the result of each operation is then the accumulator value for the next one). As this function is so general, we can do all kinds of things with it, just like implementing std::transform_if! The f function is then also called the reduce function.

A very direct implementation of transform_if will look as follows:

template <typename InputIterator, typename OutputIterator, 
          typename P, typename Transform>
OutputIterator transform_if(InputIterator first, InputIterator last,
                            OutputIterator out,
                            P predicate, Transform trans)
{
    for (; first != last; ++first) {
        if (predicate(*first)) {
            *out = trans(*first);
            ++out;
        }
    }
    return out;
}

This looks quite similar to std::accumulate, if we regard the parameter out as the init variable, and somehow get function f to substitute the if-construct and its body!

We actually did that. We constructed that if-construct and its body with the binary function object we provided as a parameter to std::accumulate:

auto copy_and_advance ([](auto it, auto input) {
    *it = input;
    return ++it;
});

The std::accumulate function puts the init variable into the binary function's it parameter. The second parameter is the current value from the source range per loop iteration step. We provided an output iterator as the init parameter of std::accumulate.. This way, std::accumulate does not calculate a sum, but forwards the items it iterates over to another range. This means that we just reimplemented std::copy without any predicate and transformation, yet.

The filtering using a predicate was added by us by wrapping the copy_and_advance function object into another function object, which employs a predicate function:

template <typename T>
auto filter(T predicate)
{
    return [=] (auto reduce_fn) {
        return [=] (auto accum, auto input) {
            if (predicate(input)) {
                return reduce_fn(accum, input);
            } else {
                return accum;
            }
        };
    };
}

This construction does not look too simple at first but have a look at the if construct. If the predicate function returns true, it forwards the parameters to the reduce_fn function, which is copy_and_advance in our case. If the predicate returns false, the accum variable, which is the init variable of std::accumulate, is just returned without change. This implements the skipping part of a filter operation. The if construct is located within the inner lambda expression, which has the same binary function signature as the copy_and_advance function, which makes it a fitting substitute.

Now we are able to filter but are still not transforming. This is done with the map function helper:

template <typename T>
auto map(T fn)
{
    return [=] (auto reduce_fn) {
        return [=] (auto accum, auto input) {
            return reduce_fn(accum, fn(input));
        };
    };
}

This code looks much easier. It again contains an inner lambda expression, which has the same signature as copy_and_advance has, so it can substitute it. The implementation just forwards the input values but transforms the right parameter of the binary function call with the fn function.

Later, when we used those helpers, we wrote the following expression:

filter(even)(
    map(twice)(
        copy_and_advance
    )
)

The filter(even) call captures the even predicate and gives us a function, which takes a binary function in order to wrap it into another binary function, which does additional filtering. The map(twice) function does the same with the twice transformation function but wraps the binary function, copy_and_advance, into another binary function, which always transforms the right parameter.

Without any optimization, we would get a horribly complicated nested construction of functions that call functions and do only a very little amount of work in between. However, it is a very simple task for the compiler to optimize all the code. The resulting binary is as simple as if it resulted from a more direct implementation of transform_if. We pay nothing in terms of performance this way. But what we get is a very nice composability of functions because we were able to stick the even predicate together with the twice transformation function, nearly as simply as if they were lego bricks.