Tracking issue for Zero/One/iter_arith stabilization

[aturon]

We currently have Zero and One traits that are meant to work with Add and Mul and support iterator operations like sum, as well as the current step_by API.

It would be good to have a more comprehensive vision for this kind of trait before stabilization; an RFC would be ideal.

[fizyk20]

Those traits would be really useful for generic arithmetics, I look forward to them being stabilized.

Also, I have some ideas for traits that would pair up with those nicely, e.g.: Field (meaning Add+Mul+Sub+Div+Neg+One+Zero), Vector<T: Field> (meaning Add+Sub+Mul<T>+Div<T>+Neg+Zero), Ring, Group etc. They would allow marking some types as behaving like fields/vectors/what have you - or would such functionality rather belong in a separate crate?

[photino]

I would like to see these are stabilized. They are really useful and simple enough to have a position in std.

[haudan]

I agree with @photino, I don't see a reason why these traits shouldn't be part of std, and like @fizyk20 said, they'll be very useful in generic arithmetics.

[aturon]

Nominating for 1.6 discussion.

[SimonSapin]

I have multiple times tried to use some_iterator.sum(), only to have the compiler remind me that it’s unstable. Then I typically replace it with something like some_iterator.fold(0, std::ops::Add::add).

Please stabilize sum. I care less about what traits support it.

[mitaa]

There is an open issue with iterator sum and product regarding type inference / default type parameter fallback (#25094)

I'm not sure how this impacts stabilization.

[alexcrichton]

Unfortunately the libs team didn't have time to decided on this in the triage meeting, so this won't enter FCP this cycle.

[sfackler]

I'd like to nominate at least Iterator::sum and Iterator::product for stabilization. I believe we can stabilize those even if we're not sure about the Zero and One traits.

[huonw]

As a general point, these traits don't necessarily cover everything one might want for non-primitives. In particular, Zero and One don't pay attention to ownership and resource reuse, e.g. some_bigint = Zero::zero() will deallocate the existing storage in some_bigint, overwriting it with the new value (maybe with a new allocation, maybe not). For performance, it can be important to reuse allocations, i.e. some_biging.set_zero().

Additionally, for other types, it may not make sense to just ask for Zero or One with no inputs, e.g. a big-float might have a notion of precision, meaning the call wants to be more like ...::zero(precision).

[adamcrume]

I agree that precision is important for big-floats, but I don't think that the notion of precision belongs in Zero. Something like set_zero(&mut self) is more interesting. It might also be nice to include is_zero(&self), because x == y where x and y are zero big-floats with different precision might return false, and because it may be possible to implement x.is_zero() to be faster than x == X.zero().

[SimonSapin]

If I’m grepping correctly, Iter::sum, Iter::product and Range::step_by are the only users of Zero or One in std’s public API. These literally only need to know:

• What’s the neutral element for Add. (Could be What’s the sum of an empty sequence.)
• What’s the neutral element for Mul. (Could be What’s the product of an empty sequence.)
• Is this step_by argument negative. (Maybe this could be part of the Step trait?)

Since we’ve already decided to reduce the scope of std::num, more features like in-place zeroing or dealing with precision probably belong in the num crate instead.

(Edited to remove truncated paragraph, it was the same as the previous one.)

[alexcrichton]

🔔 This issue is now entering its final comment period for stabilization 🔔

At the libs triage meeting we discussed that we may want to somewhat aggresively pursue stabilization of the methods here, and if it comes to it we can punt on stabilizing the traits involves (as we've done with other APIs in the past).

@aturon however I believe would like to discuss stabilizing the One and Zero traits themselves, so we can also discuss stabilizing them during this FCP.

tl;dr; This FCP is primarily for stabilizing the sum and product methods, but it's also possible to stabilize the One and Zero traits.

[bluss]

The type parameter default should be removed before stabilization, it has no effect, and the lang team seems to unfortunately doubt the future of the feature altogether.

[bluss]

@SimonSapin Your comment was cut short, but I think I agree. Zero and One are out of place as the only numeric traits in libstd. That said, it's good for everyone if One and Zero are either stabilized or removed. Unstable limbo just leads to the tricky conflicts of std's Zero vs num's Zero.

[bluss]

Zero needs a migration story. Num's Zero and libstd Zero are not compatible, and we need to make sure the transition is smooth.

[aturon]

@bluss Good catch. For the record, the difference is that num's Zero and One traits inherit from Add and Mul respectively, whereas std's don't.

Given that we want a direct connection between e.g. Zero and Add, I think inheritance makes sense, so we can make the traits match.

That issue aside, the only real question with Zero/One is: should we commit to having them in std? I think that the sum and product methods should live or die by this question: stabilizing them without eventually stabilizing the traits doesn't make sense. So to me, Zero/One stabilization is the real question here.

I agree with @SimonSapin's assessment. I also think that these traits are relatively harmless -- they are effectively specialized versions of Default. They would not be in the prelude, so I don't worry too much about conflict with a more general/powerful external numeric hierarchy.

So overall, I think I'm 👍 on stabilization of all items in question (modulo adjusting to match the num crate).

[sfackler]

If we have concerns about future compatibility with more robust numeric trait hierarchies, we can always make these traits specifically for sum and product - maybe even have them sitting in the iter module and rename them.

[SimonSapin]

How about, in std::iter:

trait Sum: Add<Rhs=Self> {
    /// Sum of an empty sequence, i.e. "zero".
    fn neutral_element() -> Self;
}
trait Product: Mul<Rhs=Self> {
    /// Product of an empty sequence, i.e. "one".
    fn neutral_element() -> Self;
}

[bluss]

@aturon I wasn't even aware of the differences in their definition. What I meant by num's Zero and std's Zero are not compatible, is simply that if my crate requires num::Zero but you implemented std::Zero, then your type does not fit the bound. Ideally we'd remove that issue, somehow.. If we can't bridge, then mya crate can never switch to std::Zero for fear of breaking deps.

[aturon]

@SimonSapin @sfackler I'm not sure I see the appeal of defining these traits so narrowly, or in iter. If we're going to have them, we may as well keep them with their more general name and placement.

@bluss I see. So, in general, we'd like to handle this by changing num to just pub use the definitions from std (which is why they need to align), but for that to work smoothly it needs to be cfg-ed on which version/what stable features are available.

[alexcrichton]

Ah one question we did have when discussing this was what to do about overflow. We no longer really have the convenience of "overflows as if you wrote the code locally" so we'll have to define semantics one way or another.

[SimonSapin]

The API we're considering for stabilization is the one proposed by @SimonSapin here which follows the collect + FromIterator pattern and precludes having a "numerical tower" hierarchy in the standard library.

I’ve just realize that this design would allow implementations to use an algorithm different from fold. For example an accurate sum of floating point numbers that avoids loss of precision by tracking multiple intermediate sums:

https://docs.python.org/3/library/math.html#math.fsum
https://code.activestate.com/recipes/393090/

But is this desirable? It looks like that algorithm allocates memory, so there’s a run-time cost to get that accuracy. This may be a trade-off better left to users to decide. Python itself provides fsum separately from sum.

So I think such an accurate sum would be better as a separate API, and it could be on crates.io at least at first. I think that the impls in std of theses traits should simply use fold with Add or Mul, and the traits documentation should recommend that other impls do the same.

This also deals with overflow semantics, doesn’t it? Leave it per-impl, but give a recommendation (and follow it in std).

[ruuda]

But is this desirable? It looks like that algorithm allocates memory, so there’s a run-time cost to get that accuracy.

You can get a significant precision win with just one extra float for which no heap allocation is required (at the cost of more arithmetic operations). But I wouln’t expect the standard library sum to do that if I didn’t ask for it explicitly. The user might care more about performance than precision, and in that case the extra operations would be undesirable. I agree that it would be better left as a separate function.

[benaryorg]

Someone did actually mention the overflow problem.

I currently have an open issue at the rfcs repo about checked (and the like) methods for Duration which made me think of the very same problem here: will there be a checked_sum method or even a trait for that? Or will I need to catch the unwinding in case of a panic?

@cuviper suggested:

Another possibility is to return Option like min/max, and the caller can use sum().unwrap_or(0). But if most callers will want that, it's not nice to be wordier with unwraps.

So we had something like:

// within Iterator
fn sum<S>(self) -> Option<S>
    where S: Add<Self::Item, Output=S>

This would also solve the overflowing problem (although it could return Result too to have distinct errors for "no elements" and "overflow").

The unwrap_or() solution would not solve the problem of having different default elements as with big floats or similar.

If for any reason you want to not use the Option version I'd support @SimonSapin's solution, even though I'd want to see some sort of overflow-checking version.

[dhardy]

This would also solve the overflowing problem (although it could return Result too to have distinct errors for "no elements" and "overflow").

I would expect vec![].iter().sum() == Some(0).

Using None like a float's NAN to indicate overflow seems reasonable from the API usage perspective.

I don't see a huge difference between Simon's last suggestion and my adjustment to his earlier suggestion in terms of how much special-purpose code needs to get added to the standard library.

Is there another possibility, to use a trait-based fold design?

trait Foldable<T, R> {
    fn initial() -> R;
    fn fold(x: T, r: R) -> Option<R>;
}

This may allow implementations like Sum and Prod to be defined in another library and a generic iterator function fn fold_with<T,R>(self, fold_t: &Foldable<T, R>) -> Option<R>. Usage would be something like:

use fold_impls::Sum;

fn main() {
    let v = vec![1, 2, 3, 4];
    println!("Sum: {}", v.fold_with(Sum).unwrap());
}

[benaryorg]

Sorry, no I meant something different and accidentally hit Ctrl while trying to get a newline somewhere, sorry for that.

First of all, current feature gated iter_arith does not have any methods for Vec<T> but only for Iterator, that means you would have to use v.iter() or v.into_iter().

This also means that your

fn fold_with<T,R>(&mut self, fold_t: &Foldable<T, R>) -> Option<R>

Should actually take ownership of the value.

Edit: current fold looks like this:

fn fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B { ... }

Furthermore, could you please explain what advantages your fold_with has over just providing some FnMut, as used by fold and an initial value?

Just use-ing it and then plugging it into the Iterator is fast to write but couldn't other crates just simply define their "special arithmetic operations" as traits and implement them for Iterator themselves?

Sorry, it might just be me not seeing the point there.

[benaryorg]

Complete enough for you?

I'd be happy if you added the where clauses to your trait, where applicable, or provided some sort of reference implementation that just/at least covered the signature of such a type.

Also how would that:

v.fold_with(sum)

work if you take fold_t using an immutable borrow?

fn fold_with<T,R>(&mut self, fold_t: &Foldable<T, R>) -> Option<R>

Wouldn't it be more like

extern crate something;

fn main() {
    let v: Vec<usize> = vec![1,2,3];
    // just to have some unified way to get such a structure `new` is used
    // because sometimes there might be an internal state to hold (for caching, or whatever reasons)
    // if this was not desirable one could simply have `let sum = something::sum::Sum;` I think
    let sum = something::sum::Sum::new();
    println!("Sum: {}", v.iter().fold_with(&sum).unwrap());
}

Edit: I just saw you corrected the use fold_impls::Sum; to be uppercase, now it makes more sense (see the comment for the unit-struct), still the immutable borrow is confusing.

[dhardy]

Thanks for your comments.

@benaryorg The reference to sum can be immutable since sum is never in fact used (except to dynamic dispatch to the right methods).

Maybe you're right that an object sum needs to be created for the type Sum implementing the trait Foldable. I've run into that limitation before. Seems silly since none of the trait functions reference the object (self).

The potential advantage of the trait is to specify two related things together (both functions of the same trait impl), but maybe it's not worth it.

[alexcrichton]

Note that at least in the past when the libs team has discussed these APIs the thought is that if we don't have the ergonomics that we have today then the methods probably aren't worth it. The sum/product methods are basically nice conveniences, and you can always write .fold(0, |a, b| a + b) yourself instead of sum if you really want.

Along those lines I don't think we want to introduce new methods like fold_with, and we've also been hesitant to attempt to over-abstract this with something like a Foldable trait or to return an Option to use the Add trait.

The thinking is that using a Sum and Product trait buys us the ergonomics we have today as well as maximal flexibility in terms of how these can be implemented. They may not always be the most ergonomic or most general to implement, but it's tough to find an alternate solution with the same level of ergonomics and flexibility.

[benaryorg]

I'll stick to @SimonSapin's solution then.

One can still check for overflows by invoking fold manually:

v.iter().fold(Some(0),|a,&b|a.and_then(|a: usize|a.checked_add(b)))

[regexident]

Just to add another use-case of One and Zero that's completely unrelated to iteration to the discussion:

While BitAnd/BitXor/BitOr/Shl/Shr/… are useful for manipulating existing binary values in a generic way One and Zero are essential and necessary for creating new binary values in a generic way (and Mul of little importance in this context).

[aturon]

I agree wholeheartedly with @alexcrichton -- at this point, with this tracking issue, we should focus on landing support for ergonomic sum and product methods analogous to collect. In the future, we can explore numeric hierarchies and other conveniences, and probably even provide blanket impls translating from one to another (given lattice impl specialization.)

[alexcrichton]

The libs team discussed this issue during triage yesterday and the decision was to stabilize. We realize that the FCP for this issue was pretty short, however, so please comment with any objections you might have! We're very willing to backport an un-stabilization for the few APIs we have this cycle.

Specifically, we're thinking of stabilizing the sum and product methods while leaving the trait they reference unstable for one more cycle (just to make sure)

[nagisa]

I feel that something monoid-identity like might not be a good match for Range, because using identity of (T, ·) with operation of (T, +) might not make complete sense ∀T. However, to me it seems like making One a trait One: Mul and Zero a trait Zero: Add (the num crate model) makes more sense than having them be stand-alone even given what I said above.

What is really desired for Range is semi-ring (T, +, ·), but I’m doubtful anybody is interested in pulling in the whole type theory into Rust.

[SimonSapin]

@alexcrichton So, stabilizing without any of the API changes proposed here?

[sfackler]

@SimonSapin No, we're moving to the collect-style helper trait: https://github.com/rust-lang/rust/pull/34530/files#diff-a9700f0b651bcc35126d8a52ae81bc78R527