accumulate and inner_product

[Anass Lasram]

In [numeric.ops] I think a third overload to accumulate and inner_product without the init parameter would allow more natural calls.

Precisely, adding something like

template <class InputIterator>
auto accumulate(InputIterator first, InputIterator last)
-> typename std::remove_reference<decltype(*first)>::type;

template <class InputIterator1, class InputIterator2>
auto inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
-> decltype( ((*first1) * (*first2)) + ((*first1) * (*first2)) );

[Vlad from Moscow]

воскресенье, 28 июля 2013 г., 5:17:21 UTC+4 пользователь Anass Lasram написал:

 As for me I do not see any usefulness of such declarations. For example if value_type of an iterator is int then usually it is better when the type of the accumulator is long long int.

In my opinion such declarations will confuse users than be helpful.

[Marc]

Yes, I also find this init parameter inconvenient on occasion, in particular because for short sequences (say 2 elements) and my own type, creating the init value and adding it can have a non-negligible cost. So I sometimes end up doing:
auto init = *first; accumulate(first+2,end,init);
or:
auto init = *first+*(first+1); accumulate(first+2,end,init);
(depends on the information I already have on the size of the sequence, and I don't write (first+n) literally)

Now I am not sure about your prototypes. It is strange not to have the version with a binary_op, although it would be hard to disambiguate. And the return types are not right. Also, it might be cool to have a way (optional) to specify the type we want for the accumulator.

[Xeo]

In general I'm inclined to agree that such overloads would be nice. In Haskell for example, there's `foldl` and `foldr` which take the operation, init value and list, but also `foldl1` and `foldr1`, which take the init value from the first element of the list.

However, I'm not sure about your declarations there. In C++14 specifically, I'd just let it stand as `auto accumulate(InIt first, InIt last);`, same for `inner_product`, and in the implementation have something along the lines of:

template<class InIt, class BinOp>
auto accumulate(InIt first, InIt last, BinOp op){
  auto acc = *first;
  while(++first != last)
    acc = op(acc, *first);
  return acc;
}

Sadly, there's another problem now: The above overload conflicts with the one that takes an `init` parameter:

template<class InIt, class T>
T accumulate(InIt first, InIt last, T init);

Which is really the same problem as providing overloads for std algorithms which take ranges,

[Matt D.]

On 7/28/2013 16:41, Xeo wrote:

In general I'm inclined to agree that such overloads would be nice. In Haskell for example, there's `foldl` and `foldr` which take the operation, init value and list, but also `foldl1` and `foldr1`, which take the init value from the first element of the list.

However, I'm not sure about your declarations there. In C++14 specifically, I'd just let it stand as `auto accumulate(InIt first, InIt last);`, same for `inner_product`, and in the implementation have something along the lines of:

template<class InIt, class BinOp>
auto accumulate(InIt first, InIt last, BinOp op){
  auto acc = *first;
  while(++first != last)
    acc = op(acc, *first);
  return acc;
}

Sadly, there's another problem now: The above overload conflicts with the one that takes an `init` parameter:

template<class InIt, class T>
T accumulate(InIt first, InIt last, T init);

Which is really the same problem as providing overloads for std algorithms which take ranges,

I'm wondering, wouldn't concepts lite solve this issue?
Overloading standard algorithms seems to be one of the envisioned use cases; in particular, see Section 2.2.1:
http://isocpp.org/blog/2013/07/new-paper-n3701-concepts-lite-a.-sutton-b.-stroustrup-g.-dos-reis

Even without concepts (lite or not), std::enable if combined with a (two argument?) version of is_callable trait restriction on BinOp should successfully eliminate the "op" version from the overload set.

// is_callable is not a part of the standard, but it's not non-trivial to implement: http://stackoverflow.com/search?q=[c%2B%2B]+is_callable

Best,

Matt

On Sunday, July 28, 2013 3:17:21 AM UTC+2, Anass Lasram wrote:

In [numeric.ops] I think a third overload to accumulate and inner_product without the init parameter would allow more natural calls.

Precisely, adding something like

template <class InputIterator>
auto accumulate(InputIterator first, InputIterator last)
-> typename std::remove_reference<decltype(*first)>::type;

template <class InputIterator1, class InputIterator2>
auto inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
-> decltype( ((*first1) * (*first2)) + ((*first1) * (*first2)) );

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.
 
 

[Xeo]

You could say the same thing for range-overloads. For the majority of cases, sure, that will be sufficient. However, what if you have a collection of function objects, which use `+` for composition and which are somehow callable just like that because they accept anything?

std::vector<my_functor> pipeline;
auto fun = std::accumulate(pipeline.begin(), pipeline.end(), my_functor::noop{});

Contrived? Maybe, but still a valid concern I think. I think I personally would prefer `std::accumulate1` (taking from `foldl1`) or `std::accumulate_over`, indicating that the range has to be non-empty since the first element of it is used as the init parameter.

[David Rodríguez Ibeas]

Just a comment on the proposed signature. While I believe deduced return types are perfectly good for user code, I would avoid them in the standard library. The advantage is that the implementor would not need to explicitly provide the return type, the disadvantage is that the return type of the function cannot be used in an SFINAE context, as it requires the instantiation of the template.

There is a single time where the algorithm is implemented in the library and infinite potential users, some that might break if this was the path taken. So the first overload from Xeo's message would be:

template <typename InputIterator, typename BinOp>

auto accumulate(InputIterator first, InputIterator last, BinOp op) -> decltype(*first);

Now, back to the original problem of adding those overloads. In the current definition the algorithms take a 'init' value that is both the initial value for the count and what will be returned to the user if the range is empty. The naïve implementation shown in this message does not account for an empty range, potentially causing undefined behavior (through the dereference of 'first', that could be easily solved by testing for an empty range before the dereference, but the question of what to return is pending. The natural choice would be a default constructed element of type 'decltype(*first)'. This choice might or not be a good choice depending on what the operator is and how the algorithm is used. Beyond that, and even if the input range is never empty, it will add an extra requirement to all uses of the algorithm, whether the range is empty or not.

Regarding the ambiguity issues of the overloads taking the operator versus a defaulted operator and no default value, these could in most cases be resolved by using SFINAE techniques to detect whether the third argument is callable with two arguments resulting from dereferencing the iterators (this could be a good example of where you could see using the result algorithm in an SFINAE context):

auto x = accumulate(v.begin(), v.end(), accumulate(l.begin(),l.end()));

    // aggregate the values in v and l

While this is not a show stopper, they should be taken in consideration while considering the added overloads.

/David

[Xeo]

On Monday, July 29, 2013 4:21:39 AM UTC+2, David Rodríguez Ibeas wrote:

There is a single time where the algorithm is implemented in the library and infinite potential users, some that might break if this was the path taken. So the first overload from Xeo's message would be:

template <typename InputIterator, typename BinOp>

auto accumulate(InputIterator first, InputIterator last, BinOp op) -> decltype(*first);

That will likely return a dangling lvalue reference - I think the appropriate course here is to use `std::decay<decltype(*first)>`. Or maybe even `typename iterator_traits<InputIterator>::value_type`.
 

The naïve implementation shown in this message does not account for an empty range, potentially causing undefined behavior

That is very much on purpose and not the "naive implementation". The whole idea is that the range is non-empty, and that is part of the pre-conditions. If the range is potentially empty, the user should either use the other overload, or make sure himself that this is not the case. This is also exactly the reason why I proposed two other names in my last message, for one solving the overload problem and also having a stronger indicator that the range needs to be non-empty.

[Róbert Dávid]

I see no intuitive way (with or without SFINAE") to figure out what the user wanted if the value_type has both an operator+ and an operator(value_type, value_type).  More so, what if one line needs this, another that? I very much like the idea, but this has to be called something different than accumulate ( inner_product is fine, as it currently requires 4 or 6 parameters, the one without init would require 3 or 5 ). We should call it "fold" (to reflect it is the same as foldl or foldr), or accumulate_over, or something like that.

After the name of the function (or the amount of parameters in case of inner_product) differ, there is no need for SFINAE tricks, it can use the trailing return type immediately. (How would you do it anyway? The last init parameter gave the convenience to know what the return type will be.)

Regards, Robert

[Vlad from Moscow]

воскресенье, 28 июля 2013 г., 5:17:21 UTC+4 пользователь Anass Lasram написал:

In [numeric.ops] I think a third overload to accumulate and inner_product without the init parameter would allow more natural calls.

In my opinion it is not a good idea because introducing such declarations will only confuse the user. It si not clear whether there is a typo in the code or it was intentional using the algorithm without the initial value.