The foundation to the Iterator is a type Item, and a method next() which returns Option<Item>:

trait Iterator {
  type Item;
  fn next(&mut self) -> Option<Self::Item>;
  // ... several elided methods
}

Annotated with comments:

trait Iterator {
  type Item;
  //   ^-- Associated type; the type we are returning each iteration
  fn next(&mut self) -> Option<Self::Item>;
  // ^    ^             ^ returns either an Item, or nothing
  // |    | it mutates something each iteration
  // | `next` method gets somehow called each iteration in for-loops

  // ... several elided methods
}

The trait signature tells us a lot about how it works:

1. We need to mutate the type for which we implement Iterator (something needs to book-keep).
2. If we have a value to yield, return Some(val)
   1. Otherwise, stop iteration by yielding None
3. We return the same type each iteration.

So now that we've seen the foundation, let's preview some Iterator trait methods for transforming iterators.

While it's nice that we can cleanly define a way to retrieve a single element at a time from a collection, it would be very nice to operate on the iterable itself. The Iterator trait provides a LOT of functions to conveniently work with iterators in a functional style. We can succinctly express more complex logic with these methods – for example:

let some_iterable = 0..100;
let sum = some_iterable
    .filter(|&e| e > 50)
    .map(|e| e * e)
    .sum();

vs

let some_iterable = 0..100;
let mut sum = 0;
for e in some_iterable {
    if !(e > 50) {
        continue;
    }
    let doubled = e * e;
    sum += doubled;
}

I personally find the first far easier to read as it requires much less parsing. This isn't always true of iterators in Rust, but most of the time it is.

Other methods we'll use for this article include Iterator::take(N), which only takes up-to N elements from the iterator. This is useful for infinite iterators, and is common in functional languages.

You can view a list of the iterator methods here.

While important, this article won't focus much on the mechanics of collect(). In short, this method uses the FromIterator trait to convert iterators into some collection. You'll find yourself using this often when working with iterators to convert them into tangible and convenient types.

There's a good example of collect() here.

Now that we've seen an overview of what's provided, we can implement Iterator!

A frequent programming task is to loop over some collection and operate (transform) the type of an element given in each iteration.

This occurs commonly when retrieving data from some source, and you need to bind the data in some useful construct (class / struct / etc). Or if you're crunching numbers you may want to operate on each element individually before some other step.

Either way, this pattern is so common that most languages offer the map construct – a way to provide an iterable and a function, and get the function applied to each element of the iterable returned.

For example, let's double each number in a vector. Rust offers a map() method on iterators, so we'll use that first:

Pseudo-code:

seq: 0, 1, 2, 3, ...
fn:  |e| e * e
out: 0, 1, 4, 9, ...

Rust:

let input = vec![1, 2, 3];
let doubled: Vec<_> = input
    .iter()
    .map(|e| e * e)
    .collect();

So we provide a function, |e| e * e which double numbers, and map implicitly takes self, which is an iterator. This may not make sense right now, so let's dig deeper into building our own Map.

Things are going to get a little higher-order here, so let's outline what we'll need:

1. We need a type Iter, which implements Iterator
2. We need a function, which maps Iter::Item to some output type Out
   1. Syntax: Iter::Item is the associated type Item from implementation of Iterator on Iter.
   2. We can express the map function in Rust then as FnMut(Iter::Item) -> Out
      1. FnMut as we're consuming the element and may want to mutate captured variables. Feel free to use Fn if you don't want that. More on this later in the Reduce section.

Putting the above together we'll need a struct to store our function and iterator:

 // Our Map struct
struct Map<Iter, Fn> {
    iter: Iter,
    f: Fn,
}

// We'll want to instantiate one later, so add a constructor method:
impl<Iter, Fn> Map<Iter, Fn> {
    fn new(iter: Iter, f: Fn) -> Self {
        Self { iter, f }
    }
}

Great, we can now tackle implementing Iterator. The first challenge is getting the types setup for our impl. As described above, we'll need an Iter, F (map fn), and Out types:

impl<Iter, F, Out> Iterator ...

But we need further guarantees as described above:

impl<Iter: Iterator, F: FnMut(Iter::Item) -> Out, Out> Iterator ...

I recommend the reader really make sure the type signature above makes sense. Rust has a tendency to hit type soup, and it is worthwhile to take a minute to understand it.

We can now implement Iterator in a straightforward way:

impl<Iter: Iterator, F: FnMut(Iter::Item) -> Out, Out> Iterator for Map<Iter, F> {
    type Item = Out;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|e| (self.f)(e))
    }
}

So we're calling next() on our stored iterator to iterate once, and mapping the value with our stored function, and returning it. This is very efficient and something that rustc / llvm love to optimize, which gives some insight into why Rust iterators are so fast.

Now that we have it, let's use it!

fn main() {
    let nat = NaturalNumbers::new().take(5);
    let seq = Map::new(nat, |e| e * e);
    for i in seq {
        println!("{}", i);
    }
}

And run it:

$ cargo run
     Compiling iterator-article v0.1.0 (/home/david/programming/iterator-article)
      Finished dev [unoptimized + debuginfo] target(s) in 0.17s
       Running `target/debug/iterator-article`
  0
  1
  4
  9
  16

Nice! We can transform sequences using our own struct. If you want to see it in action yourself, you can play with it on the rust playground.

This is certainly powerful, but it would be nice to filter the element as well. Map only has access to a single element at a time, and must operate on the element. We can play around with the function types passed but most of the time we just want to filter out certain elements.

Filter is an interesting abstraction, as it concerns itself with retaining elements of a sequence which satisfy some criteria, and dropping the rest. The criteria function, or predicate function, borrows a value from the iterator and returns true or false. If the predicate evaluates to true on an element, return it to the caller. If the predicate is false, forget about it and continue searching.

This abstraction is also very common in other languages, and is just as essential as Map for functional programming.

The other wrinkle is that we need to care about ownership in Rust. Map would want to own each element as it needs to transform it, but filter just needs to borrow the element. We won't cover the magic involved with the Fn family and references, but this will work:

FnMut(&Iter::Item) -> bool

Our job is then similar to Map, we need a struct and constructor:

// struct to hold iterator and predicate function pointer
struct Filter<Iter, Predicate> {
    iter: Iter,
    pred: Predicate,
}

// And a default constructor
impl<Iter, Predicate> Filter<Iter, Predicate> {
    fn new(iter: Iter, pred: Predicate) -> Self {
        Self { iter, pred }
    }
}

Same idea as Map – store the iterator and function in a struct. Now we can implement Iterator in a similar fashion:

impl<Iter, Predicate> Iterator for Filter<Iter, Predicate>
where
    Iter: Iterator,
    Predicate: FnMut(&Iter::Item) -> bool,
{
    type Item = Iter::Item;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(ele) = self.iter.next() {
            if (self.pred)(&ele) {
                return Some(ele);
            }
        }
        None
    }
}

We're again iterating over our underlying iterator, and then testing each element with our predicate. If it passes, we return the element. We're implicitly mutating self.iter as it's also an iterator, so no state is lost. When the caller calls next() we'll simply continue iterating where left off in self.iter and continue the process. Eventually we'll exhaust the underlying iterator and stop iteration by returning None.

So now that we have it, let's use it! We'll build off of the Map example above to retain the even elements:

fn main() {
    let nat = NaturalNumbers::new().take(10);
    let seq = Map::new(nat, |e| e * e);
    let mut seq = Filter::new(seq, |e: &u32| *e % 2 == 0);
    for i in seq {
        println!("{}", i);
    }
}

Which when run prints out (run it on the playground here):

~ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.04s
     Running `target/debug/iterator-article`
0
4
16
36
64

Great! We can now selectively retain elements in a sequence. The final tool to make is reduce (also called fold) which is the most powerful tool yet.

The motivation for reduce (fold in Rust) is pretty simple: We need a way to collapse entire sequences into some type. Map and Filter only operate on each element one a time, not an entire sequence. How would we sum all numbers in a list?

The mechanics are pretty simple thankfully:

1. We have a base type; the accumulator. In the summing example, this would be 0.
2. We have a function FnMut(acc, ele) -> acc which melds the accumulator and the given element.

For example, to multiply a list of integers we will need:

1. The accumulator, with initial value 1.
2. the function |acc, ele| acc * ele
3. A list [1, 2, 3]

We can view the computation with the table below:

So the idea is to accumulate values into the accumulator. We don't need the Iterator trait just yet, so we can implement reduce with a free standing function:

fn reduce<Acc, Iter, ReduceFn>(iterator: Iter, acc: Acc, reducefn: ReduceFn) -> Acc
where
    Iter: Iterator,
    ReduceFn: Fn(Acc, Iter::Item) -> Acc,
{
    let mut acc = acc;
    for ele in iterator {
        acc = reducefn(acc, ele);
    }
    acc
}

We can now use it:

fn main() {
    let nat = NaturalNumbers::new().take(4);
    let mut seq = Filter::new(nat, |e: &u32| *e > 0);
    let prod = reduce(seq, 1, |acc, ele| acc * ele);
    println!("{}", prod);
}

Which outputs 1 * 1 * 2 * 3 = 6 as expected (rust playground):

~ cargo run
    Blocking waiting for file lock on build directory
   Compiling iterator-article v0.1.0 (/home/david/programming/iterator-article)
    Finished dev [unoptimized + debuginfo] target(s) in 0.33s
     Running `target/debug/iterator-article`
6

reduce is strictly more powerful than Map and Filter as it has access to the whole collection and an accumulator. We can easily implement Filter in terms of reduce for example:

let mut empty_vec = vec![];
let bigger_than_five = reduce(
    NaturalNumbers::new().take(10),
    &mut empty_vec,
    |acc, ele| {
        if ele > 5 {
            acc.push(ele);
        }
        acc
    },
);

I would recommend playing around with this function. It's useful to internalize that reduce (fold) can produce any output type. However I would keep in mind that unnecessary uses of reduce like the example above removes access to the Iterator performance optimizations.