Intro

I'm not on top of traits or generics but found myself looking some of them up anyhow, and came across the Sum trait.

Here is the Std Lib documentation on Sum (I believe).

And I guess all of the generics and/or type logic and how they interoperate has thrown me for a bit of a spin ... so I thought I'd put my thoughts here. Maybe I'll work things out in writing it or maybe someone here can help me/us out?

A bit long ... sorry

Trait Definition

From the docs and source, here is the trait's signature:

// core::iter::Sum
pub trait Sum<A = Self>: Sized {
    // Required method
    fn sum<I: Iterator<Item = A>>(iter: I) -> Self;
}

First thoughts: Defined on elements not iterators?

• The part that confused me at first was what Self is actually. Naively, I imagined it was referring to the iterator (or type that'd implemented Iterator) ... but that clearly can't be true because the return type is Self.
• So ... Sum is implemented not on any collection but on the element type?!
• If so, why not rely on the Add Trait at the element level, which is responsible for the addition operator (see docs here)?

Kinda seems so?

• So, in trying to understand this, I thought I'd look at the source of Iterator::sum() first figuring that it'd be the main implementation.
  • See docs on sum() here and source code here
• This is the sum you'd be calling in something like vec![1, 2, 3].into_iter().sum() to get 6.

core::iter::Iterator::sum
fn sum<S>(self) -> S
where
    Self: Sized,
    S: Sum<Self::Item>,
{
    Sum::sum(self)
}

• Ok, so the call of Sum::sum(self) clearly indicates that this is not where Sum is defined (instead it must be in Sum::sum() somehow).
• Moreover, self is being passed into Sum::sum(), withself being the Iterator here ... which means there's no method being called on Iterator itself but something from another module.
• Additionally, this method is bound by the generic <S> which is defined in the where clause as Sum<Self::Item> ... which ... wait WTF is going on?
  • So this method (Iterator::sum()) must return a type that has implemented the trait Sum??
  • If that's correct, then that confirms my suspicion that Sum is implemented on the elements of an iterator (where I'm sure those comfortable with the generics syntax of the definition above are yelling YES!! OF course!!)
  • That's because the return type of sum() would generally have to be the same type as the summed elements, so S is both the type of the elements in the iterator and the return type of sum. All good.
  • And indeed, in the definition of the type alias S we've got Sum<Self::Item> which binds the return type of Iterator::sum() to the type of the iterator's elements (ie Self::Item)
    • Self::Item is technically the Item type of the Iterator which can, AFAIU, be defined as distinct from the type of the elements of the collection from which the iterator is derived but that's another story.

Back to the beginning

• So back to trying to understand the definition of core::iter::Sum (which I believe is the definition of the trait):

// core::iter::Sum
pub trait Sum<A = Self>: Sized {
    // Required method
    fn sum<I: Iterator<Item = A>>(iter: I) -> Self;
}

• The trait itself is bound to Sized. I don't know the details around Sized (see docs here and The book, ch 19.4 here) but it seems fundamental likely that it applies to vectors and the like.
• The generic A = Self and its occurrences in the generics for the sum() function and its return type ... are a lot:
  • AFAIU, Self, ie the type on Sum is implemented for, must be the Item type for the Iterator that will be passed into the sum method.
  • But it must also be the return type of sum() ... which makes sense.
• So the confusing part here then is the generic type of the sum() method: <I: Iterator<Item = A>>.
  • Remember, A = Self, so it's really <I: Iterator<Item = Self>> (right?)
  • This generic type is any Iterator whose Item (ie, the type that is returned each iteration) is the same type as Self.
• Which means that if I want to sum a vector if i32 numbers, I'd have to make sure I've implemented Sum not on Vec but on i32 and defined it as a method that takes any iterator of i32 (ie Self) elements to then return an i32 element.
• Ok ....

Confirmation

• We can look at the implementors of core::iter::Sum ( see docs here) and check the source for the i32 implementation ...
• Which gives us this source code:

integer_sum_product! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

• Which is using this macro defined in the same file:

macro_rules! integer_sum_product {
    (@impls $zero:expr, $one:expr, #[$attr:meta], $($a:ty)*) => ($(
        #[$attr]
        impl Sum for $a {
            fn sum<I: Iterator<Item=Self>>(iter: I) -> Self {
                iter.fold(
                    $zero,
                    #[rustc_inherit_overflow_checks]
                    |a, b| a + b,
                )
            }
        }

• which ... uses fold() (basically reduce but with an initial value) and plain addition in the anonymous/closure function |a, b| a + b. What!?

Why? How?

• Ok that was a long way to go to find the addition operator at the bottom of the heap of traits!

• Hopefully I've grasped the mechanics?!

• I'm not quite clear on why it's build this way. I'm guessing there's some flexibility baked into the way that the relevant implementation of Sum depends on the element type, which can be flexibly defined as the Item type of an Iterator independently of the type of the collection's elements. That is, an iterator can utilise a type different from the actual elements of a collection and then rely on its particular implementation of sum. And then this can be independent from Add.

• But that feels like a lot of obscure flexibility for a pretty basic operation, no?

• For example, this code doesn't compile because a type needs to be specified, presumably type inference gets lost amongst all the generics?

// doesn't compile
let x = vec![1i32, 2, 3].into_iter().sum();

// These do compile
let x2 = vec![1i32, 2, 3].into_iter().sum::<i32>();  // turbofish!!
let x3: i32 = vec![1i32, 2, 3].into_iter().sum();

• Design choices aside ...
• I'm still unclear as to how Iterator::sum() works

fn sum<S>(self) -> S
where
    Self: Sized,
    S: Sum<Self::Item>,
{
    Sum::sum(self)
}

• How does Sum::sum(self) work!?
• self is the Iterator (so vec![1i32, 2, 3].iter()).
• And Sum::sum() is the essential trait addressed above.
• How does rust go from a call of a trait's method to using the actual implementation on the specific type? I guess I hadn't really thought about it, but it makes sense and it's what all those Selfs are for.
• In this case though, it's rather confusing that the relevant implementation isn't on the type of self, but because of the definition of Sum, the implementation is on the type of the elements (or Item specifically) of self. Sighs

Thoughts??