Rust でジェネレータを作ったり、遅延評価してみる

はじめに

日本時間の2015年5月16日に Rust 1.0 がリリースされました ?? というわけで、4月末頃から、「書こう書こう」と延々と言っていた記事を、いい加減書こうと思います。

これまでの流れ

とりあえず例を見てみる

fn main() {
    let arr = [0, 1, 2, 3];  // 要素は4つしかない
    let mut iter = arr.iter();

    for _ in 0..5 {  // ループを5回回してみる
        match iter.next() {
            Some(x) => println!("{}", x),
            None    => println!("I don't have values anymore!")
        }
    }
}

このコードの出力結果は以下のようになります。

0
1
2
3
I don't have values anymore!

イテレータの内部に返すべき値 x が残っていれば、Some(x) を、残っていなければ None を返している様子がわかるかと思います。 このように、Rust のイテレータnext() メソッドは、一般に Option<T> を返します。 一方、for ... in は、イテレータから None を得た際に自動的にループを終了します。こちらも簡単な例で示しておきます。

fn main() {
    let arr = [0, 1, 2, 3];
    let iter = arr.iter();
    for i in iter {  // 0 1 2 3 と順に表示する
        println!("{}", i)
    }
}

もちろん、上の例で示したように、for i in 0..4 { ... } と書くことも可能です。 また、next() メソッドなどの、イテレータ内部の状態を変化させるメソッドを使用しない場合、変数に mut キーワードを付けて宣言する必要はありません。

Rust のイテレータについて

外部イテレータのためのインターフェースとして、std::iter::Iterator というトレイト*1が用意されており、このトレイトを実装したデータ型は、イテレータとして振る舞うことができます*2。 データ型に対してこのトレイトを実装する手順は以下の2つです。

  • Itemイテレータが返す値の型を宣言する
  • next() メソッドを実装する

next() メソッドの型シグネチャfn next(&mut self) -> Option<Self::Item> となっています。

フィボナッチ数列を返すイテレータを作ってみる

実際に、整数の二つ組を持った構造体 Fibonacci に対して、Iterator トレイトを実装してみましょう。

struct Fibonacci {
    pair: (u64, u64)
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let (a, b) = self.pair;
        self.pair = (b, a + b);

        Some(a)
    }
}

fn fib_iter() -> Fibonacci {
    Fibonacci { pair: (0, 1) }
}

next() メソッドを実行する度に、イテレータが内部の状態を変えつつ、Option<u64> 型の値を返す様子がわかるかと思います。 また、fib_iter() メソッドで、最初の2項である 0, 1 を持った Fibonacci 構造体*3を作って返すようにしています。

fn main() {
    let mut fib = fib_iter();
    println!("{}", fib.next().unwrap());
    println!("{}", fib.next().unwrap());
    println!("{}", fib.next().unwrap());
    println!("{}", fib.next().unwrap());
    println!("{}", fib.next().unwrap());
}

このコードの出力結果は以下のようになります。

0
1
1
2
3

また、main() 関数の中身を以下のように書き換えてみましょう。

fn main() {
    for i in fib_iter()
        .map(|x| x.pow(2))
        .filter(|x| x % 2 == 1)
        .take(10) {
        println!("{}", i);
    }
}

このコードの出力結果は以下のようになります。

1
1
9
25
169
441
3025
7921
54289
142129

追記 (2015年5月21日)

以下のように new メソッドみたいなのを用意してあげる方が綺麗だなと思いました。反省してます。

struct FibonacciGenerator {
    pair: (u64, u64)
}

impl FibonacciGenerator {
    fn new() -> FibonacciGenerator {
        Fibonacci { pair: (0, 1) }
    }
}

impl Iterator for FibonacciGenerator {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let (a, b) = self.pair;
        self.pair = (b, a + b);

        Some(a)
    }
}

fn main() {
    let fib_generator = FibonacciGenerator::new();
    for i in fib_generator.take(10) {
        println!("{}", i)
    }
}

*1:Haskell における型クラスのようなものと考えてもらえればいいと思います。

*2:詳細は前述のドキュメントをご覧ください。

*3:余談ですが、もちろん 0 の代わりに 2 を渡すなんてこともできるわけで、Fibonacci と言う名前は良くなかったかなとも思う。