[Перевод] Rust crashcourse. Итераторы15.12.2020 21:17

Ниже представлен перевод одной из частей серии статей 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<::Item> { todo!() }`

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

type Item = u32;

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

fn(&mut Self) -> std::option::Option<::Item>

Немного упростим. Тип входных данных — &mut Self. Однако, корректный синтаксис будет &mut self. Запутались? Просто вспомните, что &mut self — это сокращение для self: &mut Self.

fn(&mut self) -> std::option::Option<::Item>

Далее мы можем удалить квалификаторы модулей для Option и Iterator, так как они уже и так в нашей области видимости имён (namespace):

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

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

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

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

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

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

fn next(&mut self) -> Option

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

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

fn next(&mut self) -> Option {
    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 {
        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 {
        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 {
        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 {
    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 {
    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<::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 {
    iter: I,
}

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

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

impl Iterator for Doubler {
}

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

impl Iterator for Doubler {
}

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

fn next(&mut self) -> Option {
    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 Iterator for Doubler {
  |      ^^^^^^^^^^^^^^^^^^^^^^
6 | impl Iterator for Doubler {
  |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

impl Iterator for Doubler

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

impl> Iterator for Doubler

impl Iterator for Doubler
    where I: Iterator

let orig_iter = 1..11u64;

error[E0271]: type mismatch resolving ` 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>`

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

type Item = I::Item;

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 `::Item`
              found type `<::Item as std::ops::Mul>::Output`

impl Iterator for Doubler
    whereI: Iterator,
    I::Item: std::ops::Mul,

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

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

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

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

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

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

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

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(iter: I) -> I::Item
    where
    I: Iterator,
    I::Item: std::ops::Add + From,
{
    iter.fold(From::from(0u8), std::ops::Add::add)
}