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 implementedIterator
) … but that clearly can’t be true because the return type isSelf
. - 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 likevec![1, 2, 3].into_iter().sum()
to get6
.
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 whereSum
is defined (instead it must be inSum::sum()
somehow). - Moreover,
self
is being passed intoSum::sum()
, withself
being theIterator
here … which means there’s no method being called onIterator
itself but something from another module. - Additionally, this method is bound by the generic
<S>
which is defined in thewhere
clause asSum<Self::Item>
… which … wait WTF is going on?- So this method (
Iterator::sum()
) must return a type that has implemented the traitSum
?? - 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, soS
is both the type of the elements in the iterator and the return type ofsum
. All good. - And indeed, in the definition of the
type
aliasS
we’ve gotSum<Self::Item>
which binds the return type ofIterator::sum()
to the type of the iterator’s elements (ieSelf::Item
)Self::Item
is technically theItem
type of theIterator
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.
- So this method (
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 aroundSized
(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 thesum()
function and its return type … are a lot:- AFAIU,
Self
, ie the type onSum
is implemented for, must be theItem
type for theIterator
that will be passed into thesum
method. - But it must also be the return type of
sum()
… which makes sense.
- AFAIU,
- 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
whoseItem
(ie, the type that is returned each iteration) is the same type asSelf
.
- Remember,
- Which means that if I want to sum a vector if
i32
numbers, I’d have to make sure I’ve implementedSum
not onVec
but oni32
and defined it as a method that takes any iterator ofi32
(ieSelf
) elements to then return ani32
element. - Ok …
Confirmation
- We can look at the implementors of
core::iter::Sum
( see docs here) and check the source for thei32
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()
(basicallyreduce
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 theItem
type of anIterator
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 fromAdd
. -
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 theIterator
(sovec![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
Self
s 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 ofSum
, the implementation is on the type of the elements (orItem
specifically) ofself
. Sighs
Thoughts??
You are a fucking hero my friend!! Thanks so much!!
Thanks for clarifying the macro … I didn’t understand what was going on there, but it makes sense that that’s where the zero comes from.
And yea, as for the generics … I didn’t know about the default value (I was clearly reaching beyond what I could grasp!) … thanks again!!