フィボナッチ数列

イテレータの前にフィボナッチ数列のおさらいです。

次の漸化式であらわされます。

F(0) => 1
F(1) => 1
F(n) => F(n-2) + F(n-1) (n > 1)

1, 1, 2, 3, 5, 8, 13, 21, ... と無限に続きます。

思わず再帰的な実装をしたくなりますが、イテレーションの練習なので、ここは我慢してループを使ったあまり面白くない実装をします。

// fib は上限値を超えないフィボナッチ数列を表示する
pub fn fib (upper_limit:usize) {

    let mut a:usize = 0;
    let mut b:usize = 1;

    while b <= upper_limit {
        (a, b) = (b, a + b);
        print!("{} ", a);
    }
}

関数 fib は引数で与えられた「上限値」を超えないフィボナッチ数列を表示します。

// 100 を超えないフィボナッチ数列の表示
fib(100);

// 実行結果
1 1 2 3 5 8 13 21 34 55 89

イテレータでの実装

さきほどの fib 関数の実装に準じて、a / b / upper_limit のメンバ変数をもつ構造体とコンストラクタを用意します。

pub struct Fib {
    a: usize,
    b: usize,
    upper_limit: usize,
}

impl Fib {
    pub fn till(upper_limit:usize) -> Self {
        Fib {
            a: 0,
            b: 1,
            upper_limit: upper_limit,
        }
    }
}

続いて Iterator トレイトの next メソッドの実装です。

impl Iterator for Fib {
    type Item = usize;
    
    fn next (&mut self) -> Option<Self::Item> {
        // 上限値を超える場合は None を返す
        if self.b > self.upper_limit {
            return None
        }

        // 次のフィボナッチ数を計算
        (self.a, self.b) = (self.b, self.a + self.b);

        Some(self.a)
    }
}

上限値を超える場合は None を返してイテレーションの終わりをおしえます。

実行例です。

// for で各数を表示
for n in Fib::till(100) {
    print!("{} ", n);
}

// 実行結果
1 1 2 3 5 8 13 21 34 55 89

イテレータにすると処理のバリエーションが広がります。

for_each で各数を表示

Fib::till(100).for_each(|x|print!("{} ", x));

// 実行結果
1 1 2 3 5 8 13 21 34 55 89

collect でベクタ化

let fs:Vec<usize> = Fib::till(100).collect();
println!("{:?}", fs);

// 実行結果
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

map で各数を変換し、collect でベクタ化

let fs:Vec<String> = Fib::till(100).map(|x|format!("{}", x)).collect();
println!("{}", fs.join(" "));

// 実行結果
1 1 2 3 5 8 13 21 34 55 89

eumerate で各数のインデクスを付与

Fib::till(100).enumerate().for_each(|(i, x)|println!("F({})=>{}", i, x));

// 実行結果
F(0)=>1
F(1)=>1
F(2)=>2
F(3)=>3
F(4)=>5
F(5)=>8
F(6)=>13
F(7)=>21
F(8)=>34
F(9)=>55
F(10)=>89

Rust 研究：イテレータ

フィボナッチ数列

イテレータでの実装