Discussion on: Overly Functional C++: The Fold

View post

Replies for: You shouldn't need templated lambdas here; you can make fold templated and pass the same lambda you currently are. The crash is maybe caused by a ...

Thanks a bunch!

you can make fold templated and pass the same lambda you currently are

I don't quite follow - wouldn't I still need to somehow constrain the types passed to and from the lambda to types that match my input and accumulator?

You could instead take the vector by const reference and just change indices, or you could make it operate directly on the iterators.

This was actually my very first thought, but wanted to match a little more closely what a garbage-collected fold would do - probably worthwhile to actually code up both and compare!

Thanks for the tip about -02, I figured the tail recursion was at least some of the answer there.

Curtis Fenner • Oct 2 '19 • Edited

I think this should work (don't have a compiler on hand to actually run it)

template<typename T>
T fold(std::vector<T> xs, T x, std::function<T(T, T)> f)

which I think you should be able to call exactly as you were doing.

Ben Lovy • Oct 2 '19 • Edited

That was what I had, this is the error:

// Fold a binary operation over a vector
template <typename T>
T fold(std::vector<T> nums, T acc, std::function<T(T, T)> func)
{
    int length = nums.size();
    if (length == 0)
    {
        return acc;
    }
    else
    {
        int newAcc = func(acc, nums[0]);
        std::vector<T> newInput(nums.begin() + 1, nums.end());
        return fold(newInput, newAcc, func);
    }
}

// ..

int main()
{
// ..
int result = fold(nums, acc, [](int acc, int curr) { return acc + curr; });
// ..
}

foldsum.cpp:12:3: note:   template argument deduction/substitution failed:
foldsum.cpp:62:78: note:   'main()::<lambda(int, int)>' is not derived from 'std::function<T(T, T)>'
   62 |     int result = fold(nums, acc, [](int acc, int curr) { return acc + curr; });

This is probably telling me precisely what the problem is, but it's not clear to me.

Curtis Fenner • Oct 2 '19

Oh, that's interesting. You can fix it by specifying the template instantiation to use with fold<int>(......). I'm not sure exactly how the lambda ends up converting to a std::function. If you are okay with losing some information in the type signature you could also use a type parameter for the function type, making the function work with any 'callable' type.

Ben Lovy • Oct 2 '19

Ah, didn't think to try fold<int>(......). I'm also no longer near a compiler, but I'll give both of those options a go later on.

Mark Boer • Oct 2 '19

You can also add an additional template parameter BinaryOp like this:

template <typename T, typename BinaryOperation>
T fold(std::vector<T> nums, T acc, BinaryOperation op)

See the code. And its also slightly faster since std::function has some overhead.

You can have a look at std::accumulate or std::reduce, they work fairly similar and are part of the STL ;-)

Happy coding

Ben Lovy • Oct 2 '19 • Edited

Ah, thanks! I like that better, I think - good to know about std:: function.

I had come across the STL options but this exercise was specifically to get there myself :)