‎

1. Introduction
- 1.1. Attribution
- 1.2. Goals
2. Create an Iterator Decorator
3. Attaching constructors to other types
4. Type State
5. Attaching method to specific type states
6. More functions for specific type states
7. Encoding my example
8. Closing thoughts

1. Introduction

1.1. Attribution

This is a learning exercise to understand the contents of this Strange Loop video. This explanation is a poor version of the video.

1.2. Goals

Our goal is to design an API which allows us to monitor the progress through an iterator. We should be able to monitor an iterator, even if we are traversing a derived iterator.

Example: #+begin_src rust let iterator = (1..10); let derived = iterator.map(|n| n + 1).map(|n| n % 4).filter(|n| *n >= 2); for item in derived { println!("from derived: {}", item); } n#+end_src

from derived: 2
from derived: 3
from derived: 2
from derived: 3
from derived: 2

Despite iterator being used only to declare the derived iterator, I would like to see the progress of iterator when traversing derived.

2. Create an Iterator Decorator

use std::fmt::Display;

struct Verbose<Iter> {
    iter: Iter,
    cursor: u32
}

impl<Iter> Iterator for Verbose<Iter>
where Iter: Iterator, Iter::Item: Display {
    type Item = Iter::Item;


    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        if let Some(item) = self.iter.next() {
            println!("Processing {} -> {}", self.cursor, item);
            self.cursor += 1;
            Some(item)
        } else {
            None
        }
    }
}

Notice that Verbose can be defined over anything. But, if the iter field is not itself an iterator, then the Verbose instance will not be an iterator either.

let nonsense_iterator = Verbose { cursor: 0, iter: 8};
nonsense_iterator.next(); // *fails*

However, if the iter field on Iterator is an iterator, then the Verbose instance will be as well.

let it = (10..=15);
let mut v = Verbose { cursor: 0, iter: it };
v.collect::<Vec<_>>();

3. Attaching constructors to other types

Here we will define a trait that'll be implemented for any Iterator type.

trait VerboseIteratorExt<A>: Sized {
    fn verbose(self) -> Verbose<Self>;
}

impl<A> VerboseIteratorExt<A> for A where A: Iterator {
    fn verbose(self) -> Verbose<A> {
        Verbose {cursor: 0, iter: self}
    }
}

The way to read this is VerboseIteratorExt is a trait which is defined on all types A which implement Iterator. Having VeboseIteratorExt defined for a type (which all iterators do) gives that type the function verbose. When invoked, verbose produces a Verbose instance.

So now we can call verbose on any type which implements Iterator.

let iterator = (300..400).verbose().next();
println!("The result of the iterator is {}", iterator.unwrap());

But, since integers are not iterators, the following will fail to compile.

let integer: i32 = 8;
integer.verbose();

4. Type State

We would like to be able to encode different behaviors depending on the types.

use std::fmt::Display;

struct Verbose<Iter, Bound> {
    iter: Iter,
    cursor: u32,
    bound: Bound
}

trait BoundDisplay: Sized {
    fn display<I>(&self, t: &Verbose<I, Self>) -> String;
}

impl<Iter, Bound> Iterator for Verbose<Iter, Bound>
where Iter: Iterator, Iter::Item: Display, Bound: BoundDisplay {
    type Item = Iter::Item;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        if let Some(item) = self.iter.next() {
            println!("Processing {} -> {}", self.bound.display(self), item);
            self.cursor += 1;
            Some(item)
        } else {
            None
        }
    }
}

The way to read this is: Verbose can be defined over any types Iter and Bound (including nonsense types like unit, bool, etc). Any particular Verbose is only iterable if its iter field is iterable and its bound field implements BoundDisplay.

Now we need to implement a few instances of BoundDisplay and see what we can produce.

struct Finite { maximum: usize }
struct Infinite;

impl BoundDisplay for Finite { // Only reasonable on finite iterators
    fn display<I>(&self, t: &Verbose<I, Self>) -> String {
        format!("{}/{}", t.cursor, self.maximum)
    }
}

impl BoundDisplay for Infinite { // Reasonable on finite and infinite iterators
    fn display<I>(&self, t: &Verbose<I, Self>) -> String {
        format!("{}", t.cursor)
    }
}

We have two components which define different ways to display the bound of an iterator. One which is appropriate for finite and infinite iterators and one which is only appropriate for finite iterators.

let infinite = Verbose { iter: (0..5), cursor: 0, bound: Infinite };
infinite.collect::<Vec<_>>();

let finite = Verbose { iter: (0..15), cursor: 0, bound: Finite { maximum : 800 } };
finite.collect::<Vec<_>>();

There are a few things wrong here.

I do not want my API users constructing Finite and Infinite. I want to give them one simple way to construct a verbose iterator and let them move states to change the bound types.
I do not want my API to be capable of expressing lies. Presently, the maximum field of the Finite bound has no relationship to the actual length of the iterator.

5. Attaching method to specific type states

Lets add our verbose syntax from earlier, along with some methods for changing between these two states.

trait VerboseIteratorExt<A>: Sized {
    fn verbose(self) -> Verbose<Self, Infinite>;
}

impl<A> VerboseIteratorExt<A> for A where A: Iterator {
    fn verbose(self) -> Verbose<Self, Infinite> {
        Verbose { cursor: 0, iter: self, bound: Infinite }
    }
}

impl<Iter> Verbose<Iter, Infinite> where Iter: ExactSizeIterator {
    fn finite(self) -> Verbose<Iter, Finite> {
        Verbose {bound: Finite {maximum: self.iter.len()}, cursor: self.cursor, iter: self.iter }
    }
}

impl<Iter> Verbose<Iter, Finite> where Iter: Iterator {
    fn infinite(self) -> Verbose<Iter, Infinite> {
        Verbose {bound: Infinite, cursor: self.cursor, iter: self.iter }
    }
}

So now we're able to construct Verbose with syntax attached to iterators and then move between the two type states.

let mut iterator = (0..10).verbose();
iterator.next();

let mut iterator = iterator.finite();
iterator.next();

let mut iterator = (0..).verbose();
iterator.next();

And, importantly, I am disallowed from expressing a Finite Verbose when my iterator is infinite (because it will not implement ExactSizeIterator).

let mut iterator = (0..).verbose().finite(); // *fails*

6. More functions for specific type states

Using the techniques given above, I can also attach methods to only Finite/Infinite Verbose structs. Here are a few use cases for doing so:

Overriding the "Processing" string.
Attaching more formatting for only one variant.
Attaching more complicated behavior for both/one variant such as structuring the output for Tracing.

7. Encoding my example

I am now able to express my original example.

let iterator = (1..10);

// NEW
let iterator = iterator.verbose();

let derived = iterator.map(|n| n + 1).map(|n| n % 4).filter(|n| *n >= 2);
for item in derived {
    println!("from derived: {}", item);
}

I have made my base iterator verbose and so, even though I am traversing the derived iterator, I see my progress through the base iterator. I even see progress for elements which are filtered out of the derived iterator.

8. Closing thoughts

This document was produced in Emacs using org-mode. The source for this document can be found on my github page. I recommend opening this document's source in Emacs with org-mode for better syntax highlighting.

Table of Contents