Rust crashcourse. Итераторы

Ниже представлен перевод одной из частей серии статей Rust Crash Course от Майкла Сноймана, которая посвящена итераторам. Мне материал показался удачным в плане доступности изложения, поэтому перевод, сделанный для себя, решил опубликовать. Надеюсь, что это кому-то пригодится. Если данный материал будет интересен, то опубликую ещё несколько переводов из этой серии.

Так же постарался переводить максимально близко к авторскому стилю, но сократил немного междомедий и восклицаний, не сильно значимых для смысла.

Больше итераторов!

Лично для себя я обнаружил, что проще всего понять работу итераторов, написав несколько из них самому, так что с этого и начнём.

Займёмся программированием под руководством компилятора (compiler-guided). Ранее мы уже обсуждали, что существует трейт Iterator. Так что бьюсь об заклад, что нам нужно создать новый тип данных и предоставить реализацию этого трейта. Начнём с чего-нибудь простого — итератора, который не продуцирует значений вообще.

struct Empty;

fn main() {
    for i in Empty {
        panic!("Wait, this shouldn't happen!");
    }
    println!("All done!");
}

Паника (panic!()) — способ завершить текущий поток при возникновении невозможной ситуации. Это похоже на исключения (runtime exceptions) в других языках, за исключением того, что невозможно восстановить работоспособность. Так что её следует использовать только для подобных ситуаций.

Скомпилируем это и получим полезное сообщение об ошибке:

error[E0277]: `Empty` is not an iterator
 --> src/main.rs:5:14
  |
5 |     for i in Empty {
  |              ^^^^^ `Empty` is not an iterator
  |
  = help: the trait `std::iter::Iterator` is not implemented for `Empty`
  = note: required by `std::iter::IntoIterator::into_iter`

Давайте добавим пустую реализацию:

impl Iterator for Empty {
}

И получим ещё подсказку от компилятора:

error[E0046]: not all trait items implemented, missing: `Item`, `next`
 --> src/main.rs:4:1
  |
4 | impl Iterator for Empty {
  | ^^^^^^^^^^^^^^^^^^^^^^^ missing `Item`, `next` in implementation
  |
  = help: implement the missing item: `type Item = Type;`
  = help: implement the missing item: `fn next(&mut self) -> std::option::Option<<Self as std::iter::Iterator>::Item> { todo!() }`

Таким образом, нам нужно предоставить в реализации две сущности: Item и next(), которая является функцией, и к ней мы вернёмся во вторую очередь. Так что насчёт type Item? Это то, что зовётся ассоциированным типом (associated type). Он сообщает, какой тип значений продуцируется итератором. Ну так как мы ничего не продуцируем, мы можем использовать любой тип. Я буду использовать u32:

struct Empty;

impl Iterator for Empty {
    type Item = u32;
}

Ну а теперь нужно добавить что-нибудь в next. Выше в сообщении был предоставлен тип этой функции:

fn next(&mut self) -> std::option::Option<<Self as std::iter::Iterator>::Item>

Немного упростим. &mut self — это сокращение для self: &mut Self. Далее мы можем удалить квалификаторы модулей для Option и Iterator, так как они уже и так в нашей области видимости имён (namespace):

fn next(&mut self) -> Option<<Self as Iterator>::Item>

Это Self as Iterator выглядит интересно и обозначает: "возьми текущий тип и загляни в реализацию трейта Iterator". Причина, по которой мы позаботились об указании реализации в том, что следует дальше — ::Item. То, что мы на самом деле хотим выразить, звучит как "мы хотим ассоциированный тип Item, связанный с реализацией Iterator". Возможна ситуация, когда в других трейтах будут существовать ассоциированные типы с тем же самым именем, так что это просто способ однозначно сослаться на конкретный тип.

Теперь посмотрим, действительно ли это всё работает? Включим имя функции и предоставим тупое тело:

struct Empty;

impl Iterator for Empty {
    type Item = u32;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        unimplemented!()
    }
}

unimplemented!() — макрос, который использует под своим капотом panic!() и является согласованным способом предоставить реализацию в процессе активной разработки. Если у вас всё компилируется, то всё должно быть хорошо. Потом программа падает (крэшится) при выполнении из этого самого unimplemented!().

Прим. В современных версиях Rust вместо макроса unimplemented!() рекомендуется использовать макрос todo!(), о чём компилятор услужливо сообщает в подсказке при ошибке отсутствия метода next().

Мы можем ещё упростить сигнатуру функции, удалив as Iterator, который не является необходимым:

fn next(&mut self) -> Option<Self::Item>

Если хотите, так же можно заменить Self::Item напрямую на u32. Из достоинств — это короче, но недостаток в том, что если вы поменяете Item в будущем, то вам придётся менять его в двух местах. Так что это на ваше усмотрение.

Теперь предоставим реализацию. Мы возвращаем Option, который является перечислением (enum) двух вариантов: None и Some. Первый значит "у нас ничего нет", второй — "у нас есть кое-что". Исходя из этого, реализация пустого итератора, возвращающего None выглядит как то, что нам нужно:

struct Empty;

impl Iterator for Empty {
    type item = u32;
    fn next(&mut self) -> Option<u32> {
        None
    }
}

И вот так просто мы получили нашу первую реализацию Iterator.

Упражнение

Создать итератор, который будет бесконечно продуцировать число 42. Вот функция main для этого.

fn main() {
    // only take 10 to avoid looping forever
    for i in TheAnswer.take(10) {
        println!("The answer to life, the universe, and everything is {}", i);
    }
    println!("All done!");
}

struct TheAnswer;

impl Iterator for TheAnswer {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        Some(42)
    }
}

Мутабельное состояние

Сигнатура метода next включает в себя мутабельную ссылку на self. Давайте использовать её! Мы собираемся создать итератор, который считает от 1 до 10. (Если чувствуете достаточную храбрость, то попробуйте реализовать его самостоятельно, прежде, чем увидите моё решение).

struct OneToTen(u32);

fn one_to_ten() -> OneToTen {
    OneToTen(1)
}

impl Iterator for OneToTen {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.0 > 10 {
            None
        } else {
            let res = Some(self.0);
            self.0 += 1;
            res
        }
    }
}

fn main() {
    for i in one_to_ten() {
        println!("{}", i);
    }
}

Упражнение

Создайте итератор, который продуцирует последовательность чисел Фибоначчи.

struct Fibs {
    x: u32,
    y: u32,
}

fn fibs() -> Fibs {
    Fibs {
        x: 0,
        y: 1,
    }
}

impl Iterator for Fibs {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        let orig_x = self.x;
        let orig_y = self.y;

        self.x = orig_y;
        self.y = orig_x + orig_y;

        Some(orig_x)
    }
}

fn main() {
    for i in fibs().take(10) {
        println!("{}", i);
    }
}

701408733
1134903170
thread 'main' panicked at 'attempt to add with overflow', foo.rs:21:18
note: Run with `RUST_BACKTRACE=1` for a backtrace.

fn next(&mut self) -> Option<u32> {
    let orig_x = self.x;
    let orig_y = self.y;

    match orig_x.checked_add(orig_y) {
        // overflow
        None => None,

        // no overflow
        Some(new_y) => {
            self.x = orig_y;
            self.y = new_y;

            Some(orig_x)
        }
    }
}

fn next(&mut self) -> Option<u32> {
    use Fibs::*;
    match *self {
        Done => None,
        OneLeft(x) => {
            *self = Done;
            Some(x)
        }
        Running(orig_x, orig_y) => {
            *self = match orig_x.checked_add(orig_y) {
                // overflow
                None => OneLeft(orig_y),
                Some(new_y) => Running(orig_y, new_y),
            };

            Some(orig_x)
        }
    }
}

enum FibonacciIterState {
    FirstItem,
    SecondItem,
    NthItem(u64, u64),
    Overflowed,
}

struct FibonacciIterator {
    state: FibonacciIterState,
}

impl FibonacciIterator {
    fn new() -> FibonacciIterator {
        FibonacciIterator{ state: FibonacciIterState::FirstItem }
    }
}

impl Iterator for FibonacciIterator {
    type Item = u64;
    fn next(&mut self) -> Option<<FibonacciIterator as Iterator>::Item> {
        match self.state {
            FibonacciIterState::FirstItem => {
                self.state = FibonacciIterState::SecondItem;
                Some(0)
            },
            FibonacciIterState::SecondItem => {
                self.state = FibonacciIterState::NthItem(0, 1);
                Some(1)
            },
            FibonacciIterState::NthItem(prev, last) => {
                if let Some(next) = prev.checked_add(last) {
                    self.state = FibonacciIterState::NthItem(last, next);
                    Some(next)
                } else {
                    self.state = FibonacciIterState::Overflowed;
                    None
                }
            },
            FibonacciIterState::Overflowed => {
                None
            }
        }
    }
}

Адаптеры итераторов

Мы так же можем написать итератор, который будет изменять поведение существующего итератора. Давайте напишем итератор удвоитель (Doubler), который будет увеличивать в два раза значения, продуцированные предыдущим итератором. Для того, чтобы заставить это работать, мы захватим нижележащий итератор и обернём его в новый тип данных, который так же осуществляет параметризацию содержимого итератора:

struct Doubler<I> {
    iter: I,
}

Давайте заглянем в функцию main, чтобы показать, как это используется:

fn main() {
    let orig_iter = 1..11; // итератор от 1 до 10
    let doubled_iter = Doubler {
        iter: orig_iter,
    };
    for i in doubled_iter {
        println!("{}", i);
    }
}

Если скомпилировать это, то получим ошибку из-за отсутствия реализации трейта Iterator. Напишем её:

impl Iterator for Doubler {
}

При компиляции получаем сообщение об ошибке:

error[E0107]: wrong number of type arguments: expected 1, found 0
 --> src/main.rs:6:19
  |
6 | impl Iterator for Doubler {
  |                   ^^^^^^^ expected 1 type argument

Ок, это звучит разумно. Doubler сам по себе не является типом до тех пор, пока мы не зададим его параметры. Так что сделаем это:

impl Iterator for Doubler<I> {
}

Получили два сообщения об ошибках. Можете посмотреть на второе, но это не слишком полезно. (Рекомендация: сначала всегда смотрите на первое сообщение об ошибке и пытайтесь её исправить прежде, чем двигаться дальше).

Первое сообщение:

error[E0412]: cannot find type `I` in this scope
 --> foo.rs:5:27
  |
5 | impl Iterator for Doubler<I> {
  |                           ^ not found in this scope

Так что же происходит? Когда мы предоставляем реализацию, нам нужно указать все типовые переменные, которые хотим использовать заранее. Сделаем так:

impl<I> Iterator for Doubler<I> {
}

Это может выглядеть избыточно (как и для меня поначалу), но в конечном счёте у вас будут более сложные случаи, и эти два набора угловых скобок не будут одинаковыми.

Теперь мы приблизились к решению, и компилятор ругается на отсутствие type Item и next. Двинемся дальше и вернём u32 снова:

type Item = u32;
fn next(&mut self) -> Option<u32> {
    unimplemented!()
}

Уже компилируется и запускается, а затем падает на unimplemented!. Отлично, есть прогресс!
Трюк здесь в том, что мы хотим попросить следующее значение у нижележащего итератора. Так что сделаем это с помощью явного сопоставления шаблонов (для функциональщиков: да, здесь тоже есть метод map у типа Option, который можно использовать):

fn next(&mut self) -> Option<u32> {
    match self.iter.next() {
        None => None,
        Some(x) => Some(x * 2),
    }
}

Достаточно симпатично, но при компиляции получаем:

error[E0599]: no method named `next` found for type parameter `I` in the current scope
 --> src/main.rs:9:25
  |
9 |         match self.iter.next() {
  |                         ^^^^ method not found in `I`
  |
  = help: items from traits can only be used if the type parameter is bounded by the trait
help: the following traits define an item `next`, perhaps you need to restrict type parameter `I` with one of them:
  |
6 | impl<I: std::iter::Iterator> Iterator for Doubler<I> {
  |      ^^^^^^^^^^^^^^^^^^^^^^
6 | impl<I: std::str::pattern::Searcher> Iterator for Doubler<I> {
  |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Компилятор знает, что мы наверное имеем в виду метод next из трейта Iterator. Но он не использует его. Можно задаться вопросом, почему же так происходит. Потому что мы не сказали компилятору, что эта реализация трейта существует! Нам нужно указать, что параметр I должен иметь реализацию трейта Iterator.

impl<I: Iterator> Iterator for Doubler<I>

Это немного новый синтаксис, но достаточно прямолинейный: I должно иметь реализацию трейта Iterator. К сожалению, это ещё не всё, что нам нужно:

error[E0369]: cannot multiply `{integer}` to `<I as std::iter::Iterator>::Item`
  --> src/main.rs:11:31
   |
11 |             Some(x) => Some(x * 2),
   |                             - ^ - {integer}
   |                             |
   |                             <I as std::iter::Iterator>::Item
   |
   = note: the trait `std::ops::Mul` is not implemented for `<I as std::iter::Iterator>::Item`

Обсудим этот момент. I — это какой-то Iterator, что мы уже установили. И мы знаем, что значение x, которое мы используем в x * 2 будет ассоциированным с I типом Item. Проблема в том, что мы понятия не имеем, какой это будет тип, и поддерживает ли он операцию умножения!

Уже говорилось, что мы собираемся продуцировать тип u32, так что можем ли мы принудительно указать, что Item является типом u32? Да!

impl<I: Iterator<Item=u32>> Iterator for Doubler<I>

Юху, наш код работает!

Альтернативный синтаксис: ключевое слово where

Поскольку ограничения становятся всё более сложными, указание их всех в параметрах в начале impl начинает выглядеть перегруженным. Вы можете использовать where как альтернативу для этого:

impl<I> Iterator for Doubler<I>
    where I: Iterator<Item=u32>

Люди руководствуются субъективной точкой зрения при принятии решения на переход к этой конструкции. Лично я предподчитаю единообразие (consistency) краткости, и почти всегда использую where. Вы можете придерживаться своего взгляда. Так же вы должны знать оба синтаксиса для чтения чужого кода.

Не только u32

Немного странно, что мы привязались к u32 типу. Что, если мы поменяем нашу функцию main вот так:

let orig_iter = 1..11u64;

Получим ошибку компиляции:

error[E0271]: type mismatch resolving `<std::ops::Range<u64> as std::iter::Iterator>::Item == u32`
  --> src/main.rs:24:14
   |
24 |     for i in doubled_iter {
   |              ^^^^^^^^^^^^ expected `u64`, found `u32`
   |
   = note: required because of the requirements on the impl of `std::iter::Iterator` for `Doubler<std::ops::Range<u64>>`

Возможно ослабить это ограничение, но ценой некоторого усложнения. Но давайте сделаем это! Удалим все указания на u32 из нашей реализации. Вот первая попытка:

impl<I> Iterator for Doubler<I>
    where I: iterator
{
    type Item = ???;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            None => None,
            Some(x) => Some(x * 2),
        }
    }
}

Я заменил все Option<u32> на Option<Self::Item> и удалил <Item = u32> у I: Iterator. Но что нужно указывать для type Item=? Хочется, чтобы оно было тем же типом, что и Item у нижележащего итератора. Так давайте так и укажем!

type Item = I::Item;

Работает! Но всё ещё не компилируется, потому что компилятор не знает, как выполнять операцию умножения для I::Item. К счастью, есть трейт Mul для типов, которые поддерживают умножение. Мы можем добавить его:

where
I: Iterator,
I::Item: std::ops::Mul,

Новое сообщение об ошибке:

error[E0308]: mismatched types
  --> foo.rs:14:29
   |
14 |             Some(x) => Some(x * From::from(2u8)),
   |                             ^^^^^^^^^^^^^^^^^^^ expected std::iter::Iterator::Item, found std::ops::Mul::Output
   |
   = note: expected type `<I as std::iter::Iterator>::Item`
              found type `<<I as std::iter::Iterator>::Item as std::ops::Mul>::Output`

Оказывается, у трейта Mul есть ассоциированный тип для выходного значения. Это полезно для выражения более сложных отношений на уровне типов. Например, мы можем определить типы для Силы (Force), Массы (Mass) и Ускорения (Acceleration), а затем определить реализацию трейта Mul, которая умножает тип Масса(Mass) на тип Ускорение(Acceleration), и порождает значение типа Сила(Force).

Это замечательная фича, но она нам здесь лишь мешает. Мы хотим лишь сказать, что тип выходного значения должен быть тот же, что и у item:

impl<I> Iterator for Doubler<I>
    whereI: Iterator,
    I::Item: std::ops::Mul<Output=I::Item>,

И теперь уже получаем:

error[E0308]: mismatched types
  --> foo.rs:14:33
   |
14 |             Some(x) => Some(x * 2),
   |                                 ^ expected associated type, found integral variable
   |
   = note: expected type `<I as std::iter::Iterator>::Item`
              found type `{integer}`

Ух. У нас есть 2, которое может быть каким-нибудь встроенным типом. Но мы не знаем, что Item является каким-то встроенным типом. Я не знаю, как задать ограничение так, чтобы этот код работал (если кто знает — пишите, я обновлю текст). Один трюк, который работает, заключается в расширении (upcast) типа u8 при помощи трейта From, который выполняет безопасные числовые преобразования (которые не могут привести к переполнению или усечению).

impl<I> Iterator for Doubler<I>
    where
    I: iterator,
    I::Item: std::ops::Mul<Output=I::Item> + From<u8>,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            None => None,
            Some(x) => Some(x * From::from(2u8)),
        }
    }
}

Фух, наконец-таки закончили!

Упражнение

Более простое задание к вышеописанному — использовать x + x вместо x * 2. Перепишите итератор для этого. Подсказка: компилятор не будет знать, что ему можно делать копии заданного типа до тех пор, пока ему не сообщить об этом через указание соответствующего трейта.

impl<I> Iterator for Doubler<I>
    where
    I: Iterator,
    I::Item: std::ops::Add<Output=I::Item> + Copy,
{
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            None => None,
            Some(x) => Some(x + x),
        }
    }
}

Резюме

Получилось много. Надеюсь, это все дало идеи, как работают итераторы. Мы можем писать обобщённые адаптеры, которые будут работать со множеством типов данных. Вы можете применить Doubler к итератору диапазона, как мы это и сделали. Вы так же можете применить его к пустому итератору Empty, который писали ранее. Или к дюжинам других итераторов.

Вы можете заметить, что типы этих итераторов разрастаются по мере того, как вы добавляете больше возможностей в них. Это действительно так, и это так и задумано. Статически представляя тип полный тип, компилятор может видеть все действия, которые выполняются в конвейере опеций итераторов, и очень хорошо их оптимизировать.

Больше идиоматичности

Адаптер Doubler, который мы написали, не идеоматичен вообще. Вот как это делается в реальной жизни:

fn main() {
    for i in (1..11).map(|x| x * 2) {
        println!("{}", i);
    }
}

Трейт Iterator включает в себя множество вспомогательных методов, которые могут быть собраны в длинную цепочку действий. Например:

fn main() {
    for i in (1..11).skip(3).map(|x| x + 1).filter(|x| x % 2 == 0) {
        println!("{}", i);
    }
}

Вы можете написать подобное как цикл на C/C++, но:

• Будет сложнее проследить логику
• Будет сложнее расширить возможности в будущем
• Это не будет быстрее: компилятор оптимизирует такие к тому же развёрнутому коду, который вы можете написать руками

Коллекционирование результатов

Вы можете собрать результаты работы итератора в вектор:

fn main() {
    let my_vec: Vec<u32> = (1..11).collect();
    println!("{:?}", my_vec);
}

Указание типа тут необходимо, так как collect может работать со множеством различных типов данных.

Упражнение

Используйте метод fold для получения суммы чисел от 1 до 10. Дополнительно: напишите вспомогательную функцию sum.

fn main() {
    let res = (1..11).fold(0, |x, y| x + y);
    println!("{}", res);
}

fn main() {
    let res = (1..11).fold(0, std::ops::Add::add);
    println!("{}", res);
}

fn sum<I>(iter: I) -> I::Item
    where
    I: Iterator,
    I::Item: std::ops::Add<Output=I::Item> + From<u8>,
{
    iter.fold(From::from(0u8), std::ops::Add::add)
}