deduce argument type from its iterator

Question

I'm trying to implement the Haskell function foldr in C++:

template <typename F, typename ForwardIter, typename B>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end)
{
    if (begin == end) {
        return z0;
    } else {
        auto lval = *begin;
        return f(lval, foldr(f, z0, ++begin, end));
    }
}

My question is. Can I deduce the type F to std::function using info from ForwardIter? Imaginary type: F = std::function<B(typename ForwardIter::value, B)>

Considering the Haskell signature (a->b->b)->b->[a]->b that indicates the relationship between arguments, I'm wondering if there is one way to specify this kind of relationship in C++. So that when I incidentally passing a wrong functor to 1st argument, the compiler would tell me that she need a functor with exact signature.

Answer 1

Considering the Haskell signature (a->b->b)->b->[a]->b that indicates the relationship between arguments, I'm wondering if there is one way to specify this kind of relationship in C++.

Yes, there is. You are misguided in thinking that one does that with std::function, though. std::function is a container for callables with a known signature. Why would one wrap stuff in a container just for passing it as an argument?

You can simply use a trailing return type, for example:

template<typename F, 
         typename ForwardIter, 
         typename B,
         typename ValueType = typename std::iterator_traits<ForwardIter>::value_type>
auto foldr(F f, B z0, ForwardIter begin, ForwardIter end)
-> decltype(std::declval<F&>()(std::declval<ValueType&>(), std::declval<B&>())) { ...

You can also define a trait for your requirements (i.e. F is callable with an argument of the value_type of the iterator and another of typeB, and returning B), and use that trait to reject other callables.

template<typename F, 
         typename ForwardIter, 
         typename B>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end)
{
    using ValueType = typename std::iterator_traits<ForwardIter>::value_type;
    static_assert(is_callable<F&, B(ValueType&, B&)>(), "F must be callable with signature B(B, B)");
    ...

This will cause an error if the object is not callable with the right signature. If you only want the overload to be excluded from overload resolution you can use SFINAE with enable_if

template<typename F, 
         typename ForwardIter, 
         typename B,
         typename ValueType = typename std::iterator_traits<ForwardIter>::value_type,
         typename std::enable_if<is_callable<F&, B(ValueType&,B&)>::value, int>::type = 0>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end) { ...

Or you can use that trait for tag dispatching. Or whatever. The important bit is that this is not what std::function was made for (and it's not just a problem of runtime overhead; it also makes certain code fail to compile when it would work just fine without the std::function obsession).

---

All that said, if I was writing this function, I would start more or less like this (note all the reference semantics and forwarding going on):

template<typename F, 
         typename It, 
         typename B,
         typename Reference = typename std::iterator_traits<It>::reference,
         typename std::enable_if<is_callable<F&, B(Reference&&,B)>::value, int>::type = 0>
B foldr(F&& f, B&& z0, It first, It last)
{
    if (first == end) {
        return std::forward<B>(z0);
    } else {
        auto&& r = *first; // must do here to avoid order of evaluation woes
        // don't forward f because we cannot "destroy" it twice, i.e. no moving!
        return f(std::forward<decltype(r)>(r), foldr(f, std::forward<B>(z0), ++first, end));
    }
}