遅延評価を使えばこういう風にフィボナッチ数列を表現できるよ、という話。

普通は(正格評価の場合)、次のような求め方をしますね。

int fib(int n) {
    if(n < 2) {
        return 1;
    } else {
        return fib(n-2) + fib(n-1);
    }
}

DP使えば別の方法ももちろんありますが、省きます。

遅延評価を使って書くと、次のように書けます。Clojureです。

(def fibs (lazy-cat [0 1] (map + (rest fibs) fibs)))

短いですね。順を追って説明しましょう。

まずlazy-catですが、これはシーケンスの連結(concat)です。ただし遅延評価のシーケンスを返します。

(lazy-cat [1 2 3] [4 5 6])
=> (1 2 3 4 5 6)

つまりfibsは、[0 1]と(map + (rest fibs) fibs)の結果が連結されたものということです。 mapに第3引数以降を与えると次のような動作をします。

(map + [1 2 3] [2 3 4])
=> (3 5 7)

さて、fibsの0番目の要素が欲しいとき、その値はもちろん0です。同様に1番目の値は1です。問題は2番目以降の値を取得する時ですね。

1番目までしか値が分かっていないとき、fibsは

fibs = [0 1 ...]
(rest fibs) = [1 ...]

…の部分が未確定部分です。

(map + (rest fibs) fibs)の最初の計算では(rest fibs)とfibsの0番目の要素同士を足し算するので1+0=1となり、fibsの2番目の値が確定します。

fibs = [0 1 1 ...]
(rest fibs) = [1 1 ...]

(map + (rest fibs) fibs)の2回目の計算では(rest fibs)とfibsの1番目の要素同士を足し算するので1+1=2となり、fibsの3番目の値が確定します。

fibs = [0 1 1 2...]
(rest fibs) = [1 1 2...]

以降同じことの繰り返しです。fibsの要素はその値が必要になるまで計算されない(遅延評価なので当然)ので、先のワンライナーのfibsの定義だけで無限に続くフィボナッチ数列を全て表現できています。

この定義の仕方をはじめて見たときは感動で涙腺が緩んだのを今でも覚えてます。

遅延評価って便利ですね。