Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Rust のイテレータを使いこなしたい

最近、 Project Euler を Rust でコツコツと解いているのですが、イテレータ（Iterator）を使いこなせるときっといい書き方ができそうだなあと思う場面が多く、イテレータに改めて入門したいと思いこの記事を書きます。

書き始めていまいちまとまりのない感じになってしまいましたが、せっかく書き始めたので記事を公開して供養しておきます。

内容は、公式ドキュメントか、『プログラミング Rust』に大きくよっています。それらからヒントを得ながら自身でまとめ直した記事です。

今回の記事は Java や Scala に前提がある方向けに書いています。一方で、その他の言語出身の方でもある程度お楽しみ頂ける内容にはなっていると思います。イテレータのコンセプトは、言語間でそう大差ないはずだからです。

イテレータとは何か

イテレータとは一連の要素（ベクタ、リスト、文字列、ハッシュマップなど）に対して順番に操作を行う抽象構造をいいます。典型的には、for ループで回している処理はイテレータで表現可能です。先頭から順番に、イテレータ内の要素を捜索し終わるまで順番に連続して、指定した操作をかけていくことができます。

外部と内部

イテレータには外部イテレータと内部イテレータが存在します。まず一言で説明すると次のような説明になるでしょう:

他の言語での例を知るために、 Scala コードを見ながら実装を確認していきましょう。

外部イテレータは、Iterator インタフェースと Iterable インタフェースの両方を駆使しながら実装します。Iterator インタフェースは、次の要素が存在するかを確認し、存在すれば次の要素を取り出します。Iterable インタフェースは、そのデータがイテレーション可能な構造をもっているかどうかを示すインタフェースです。イテレータを返すメソッドをひとつもっています。

trait Iterator[E] {
  def hasNext: Boolean
  def next: E
}

trait Iterable[E] {
  def iterator: E
}

これらを組み合わせて IntegerList というイテレート可能なデータ構造と、IntegerListIterator というイテレータを実装します。IntegerList#iterator() によってイテレータを取り出し、IntegerListIterator#hasNext() と IntegerListIterator#next() によって、イテレート処理そのものを実装します。

case class IntegerList(array: Array[Int]) extends Iterable[Int] {
  override def iterator: Int = IntegerListIterator(array)
}

case class IntegerListIterator(array: Array[Int]) extends Iterator[Int] {
  private var index: Int = 0
  override def hasNext: Boolean = index < array.length
  override def next: Int = {
    val r = array(index)
    index = index + 1
    r
  }
}

使う場合には、

object Main extends App {
  val list = IntegerList(Array(1, 2, 3, 4, 5, 6))
  val iterator = list.iterator
  while(iterator.hasNext) {
    println(iterator.next)
  }
}

このように、while ブロックの条件の箇所に hasNext() を使用し、true である限りはイテレータの要素を取り出すという処理を書けば、イテレータはこれで実装できます。外部イテレータでは、while や for などの制御構文の力を借りながらイテレータを実装するわけです。

一方で内部イテレータの場合は少し事情が異なります。内部イテレータの場合、イテレート可能なデータが、イテレーションに関する処理を行うメソッドを内部にもっています。具体的には forEach といった関数がそれです。内部イテレータを実装する場合には、forEach メソッドがどのような処理を行うかを外から注入する必要が出てくるため、クロージャなどの自身で環境を新たに作る機能が追加で必要になります。

イテレート可能なことを示すインタフェースは、たとえば次のように実装できます。先ほどとは違い、forEach 関数が生えていてそこに行いたい処理を投げ込むとイテレータを実装できます。

trait Iterable[E] {
  def forEach(e: E => Unit): Unit
}

case class IntegerList(ints: Array[Int]) extends Iterable[Int] {
  override def forEach(e: Int => Unit): Unit = {
    for (i <- ints) {
      e(i)
    }
  } 
}

実行時は次のようになるでしょう。その際、実行サイドでは制御構文の助けは実質借りていません。

object Main {
  val list = IntegerList(Array(1, 2, 3, 4, 5, 6))
  list.forEach(i => println(i))
}

Rust におけるイテレータ

IntoIterator と Iterator

たとえば Vec<T> 型に生えているイテレータを見てみましょう。すると、2つのイテレータの利用方法があるとわかります。into_iter() というメソッドと、iter() というメソッドの両方が利用可能です。これらには、一体どのような違いがあるのでしょうか。

iter() というメソッドは、Iterator トレイトが司っています。Iterator トレイトは、次の値があるかどうかを確認しある場合は取り出す next() メソッドを保持しています。next() は、次の値が存在すれば Some を返し、そうでない場合は None を返してそのイテレーションが終了したことを示します。

Iterator の中で今回扱う内容をおおよそ理解するために必要なシグネチャを抜き出しておきます。なお、Iterator は map や filter などの「アダプタ」と呼ばれる関数群を保有しており、これらを使いこなすとイテレータを使いこなし始めたとようやく思えるようになってきます。今回の記事ではすべては紹介しませんが、この記事では網羅的にさまざまなアダプタを紹介しています。

pub trait Iterator {
    type Item;

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

into_iter() というメソッドは、IntoIterator トレイトが司っています。このトレイトは、「どのようにイテレータに変換されるか」を定義するトレイトです。IntoIterator を実装するすべての型は、「イテレート可能（iterable）である」と呼ばれます。先ほどの例の対応関係では、Iterable インタフェースがそれです。このトレイトが実装されていると、Rust のループに関する制御構文（for など）を使用して、イテレータの中身を走査することができます。

IntoIterator も同様に、今回扱う内容をおおよそ理解するために必要なシグネチャを抜き出しておきます。

pub trait IntoIterator {
    type Item;

    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
(...)
}

Rust の for ループは IntoIterator と Iterator の各々のメソッドの呼び出しを短く書いたものに過ぎません。ベクタ Vec<T> は Iterator と IntoIterator を実装していますが、これらを操作するためには次のように実装できます。下記は先ほどの外部イテレータに該当する処理です。

let fibonacci = vec![1, 1, 2, 3, 5, 8];
for i in &fibonacci {
    println!("{}", i);
}

Rust における for ループは、内部的には次のように展開されて解釈されています。

let mut fib_iter = (&fibonacci).into_iter();
while let Some(i) = fib_iter.next() {
    println!("{}", i);
}

for ループは、対象となる &fibonacci を IntoIterator::into_iter() を使ってイテレータ（Iterator）に変換し、その後 Iterator::next() を繰り返して呼び出しています。into_iter() すると、Vec はムーブされる点に注意が必要です。Iterator::next() は先ほども見たとおり、要素があれば Some、要素がなければ None を生成します。None の場合は実質終了判定のため、そこで処理が終了するというわけです。これが Rust における外部イテレータの全貌です。

Rust におけるイテレータは最適化の対象になります。アダプタも静的ディスパッチが走るため、躊躇せずに利用することができます。むしろ、最適化の観点から見ると、躊躇せずにイテレータを利用していくことが Rust では重要だと言えるでしょう。

フィボナッチ数列を内部イテレータで表現する

実際に Project Euler の問題を解いて、イテレータを理解してみましょう。今回は下記の問題を題材にします。和訳はこちらのサイトより引用しております。

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

フィボナッチ数列は、前後の数を足して次の数を生成するというのが基本的なロジックです。したがって、2つの数を持つ構造体を作成し、それに対する Iterator を実装することで、フィボナッチ数列のイテレータを実装できます。

struct Fibonacci {
    a: i64,
    b: i64,
}

impl Fibonacci {
    // 初期化を行います。
    fn new() -> Fibonacci {
        Fibonacci { a: 0, b: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = i64;
    // a, b の情報を元に次の数字を計算します。
    fn next(&mut self) -> Option<i64> {
        let x = self.a;
        self.a = self.b;
        self.b += x;
        Some(x)
    }
}

これでイテレータは作成できました。あとは、「数値の項が400万以下の」「偶数の項の」「総和」を、アダプタ（それぞれ左から順に、take_while、filter、sum に対応）を用いて実装すれば実装は完了です。

fn main() {
    let s: i64 = Fibonacci::new()
        // 偶数の項のみに絞る
        .filter(|&f| f % 2 == 0)
        // 400万までのフィボナッチ数列に絞る
        .take_while(|&f| f <= 4_000_000)
        // 総和を算出する
        .sum();
    println!("{}", s);
}

フィボナッチ数列のような数列もイテレータで生成できてしまいますし、さらにそこから数列の絞り込みや上限以下の数列の取得、合計の取得なども、アダプタを用いれば行うことができてしまいます。何より Rust は、こうしたアダプタにも最適化が走るというのが驚異的な点でしょう。

github.com

このリポジトリのコミット履歴をたどると、パフォーマンスがまったく出なかった最初の実装例も見ることができます。笑。

まとめ

  • Rust には Iterator トレイトと IntoIterator トレイトが用意されていて、それらを使うとイテレータを利用できる。
  • Iterator には map や filter などのアダプタと呼ばれる関数群が用意されている。それらは最適化が走るので、追加コストを気にすることなく利用できる。
  • フィボナッチ数列を Iterator を用いて表現し、アダプタで Project Euler の問題を解くというサンプルを確認した。

レッツイテレータライフ🙆‍♀️❤️