Implement `Sum` and `Product` for `Saturating<T>`

[neverRare]

Proposal

Problem statement

Many numeric types implement Sum and Product, which allows the use of convenient sum and product methods in Iterators, except for Saturating types however, we're forced to use fold or other methods. Sum and Product could also have optimized implementation unlike fold.

Motivating examples or use cases

Using Sum would be useful for performing addition for images where we simply add the values of the pixels, saturating is desirable here.

Solution sketch

impl Sum for Saturating<u8> {
    fn sum<I: Iterator<Item = Self>>(mut iter: I) -> Self {
        iter.try_fold(Self(0), |sum, value| {
            if sum == Self::MAX {
                None
            } else {
                Some(sum + value)
            }
        })
        .unwrap_or(Self::MAX)
    }
}
impl Sum for Saturating<i8> {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(Self(0), Add::add)
    }
}
impl Product for Saturating<u8> {
    fn product<I: Iterator<Item = Self>>(mut iter: I) -> Self {
        iter.try_fold(Self(1), |product, value| {
            if value.0 == 0 {
                None
            } else {
                Some(product * value)
            }
        })
        .unwrap_or(Self(0))
    }
}

I think we have to use macros to easily implement this across all possible types.

Summing unsigned type could be optimized: whenever we reached the max value, we could stop the iteration and just return the max value. Thanks to Echo for pointing this out.

The same is true for finding the product, if we reached 0, we stop the iteration and return that.

Alternatives

It's possible to use fold, however, having sum and product is convenient.

Links and related work

None

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[eggyal]

Duplicate of #303