CODEWITHSUNDEEP
c++templatestypename
Yang Liu
Yang Liu

Reputation: 173

deduce argument type from its iterator

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.

Upvotes: 2

Views: 288

Answers (4)

R. Martinho Fernandes
R. Martinho Fernandes

Reputation: 234514

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));
    }
}

Upvotes: 6

Simon Richter
Simon Richter

Reputation: 29598

You can use typename std::iterator_traits<ForwardIter>::value_type if either

  • the iterator has a member typedef ... value_type;, or
  • an appropriate specialisation of iterator_traits exists (e.g. for pointers).

Upvotes: 0

Tristan Brindle
Tristan Brindle

Reputation: 16824

Yes, it would be possible. The advantage is that if you call foldr repeatedly with many different functions, but the same types for ForwardIterator and B, you will only get one version of the generated code, and thus (potentially) a smaller executable.

However, my instinct says "don't do it". Precisely because of the generic properties of std::function, the compiler has little chance of inlining your call to f(); in turn, it may have difficulty unwinding the recursive call to foldr. On the other hand, if you allow it to synthesize a specialized foldr for each function, you've got a much better chance of getting a highly optimised implementation. This is particularly true if f is something simple, like std::plus or something similar.

For example, trying the following with Clang 3.1 at -03:

std::vector<int> v{1, 2, 3, 4};
std::cout << foldr(std::plus{}, 5, v.begin(), v.end()) << std::endl;

leads to the call to foldr being completely eliminated. A version of the same code using std::function has much more overhead.

Of course, instinct and gut feeling are particularly terrible ways of deciding whether or not to do something, and that goes double when C++ templates get involved. I would suggest trying both approaches and seeing which turns out better.

Upvotes: 2

NicholasM
NicholasM

Reputation: 4673

Use the decltype keyword. The use of auto in your code suggests you are using C++11. At the top of your function:

typedef decltype(*begin) ForwardIterValue;          // type of result of applying dereference operator
typedef std::function< B(ForwardIterValue, B) > F;  // desired function object

As the wikipedia entry says,

Its primary intended use is in generic programming, where it is often difficult, or even impossible, to express types that depend on template parameters

Depending on how you construct the function object, using auto for that as well might be possible.

Upvotes: 2

Related Questions