JavaScript (TypeScript) で配列の遅延評価

「Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド」（以下、 FP in Scala）という本を読んでいます。
ところどころプログラミングの演習問題が出てきて、これを解いていかないとちゃんと理解できなさそうなのですが、 Scala で書くのも当たり前すぎてつまらない（？）ので、 JavaScript (TypeScript) で書いてみようと思いました。
今回は第5章に出てくる遅延評価を取り上げます（次回があるかどうかは分かりません）。
コードは以下に公開しています。

• https://github.com/kimamula/fp-in-javascript/tree/master/lazy-array

遅延評価とは

「実際に必要になるまで、値の評価を遅延させる」ことです。 Haskell はデフォルトで遅延評価ですし、 Scala でも明示的に宣言することで遅延評価を使えます。
その効果を理解するうえで分かりやすいのが、遅延評価を配列（リスト）に適用することです。

配列を遅延評価するメリット

無限長の配列を扱うことができる

Haskell ではたとえば、 偶数を小さい順に並べた無限長のリストを以下のように生成できます。

let evens = [2,4..] 

evens は無限長のリストですが、評価が遅延されるため、メモリをほとんど消費しません。たとえば、 evens の 10 番目の数字は 20 ですが、それは実際にその値を参照した際に初めて計算されます。
もちろん、一度評価された値は使い回されるため、再度参照された際に再計算されることはありません。

Collection API を繰り返し実行した際に、一時的なリストの生成やそれに対するループが発生しない

FP in Scala に登場する例ですが、たとえば以下のようなコードを実行したとき、

List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

実際には以下のような順序で計算が行われます。

List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

List(11,12,13,14).filter(_ % 2 == 0).map(_ * 3)

List(12,14).map(_ * 3)

List(36,42)

map や filter が実行されるたびに、その時点で一時的なリストが生成されループにより走査されます。
これは、 map や filter が、それぞれの実行タイミングで計算をやり遂げてしまうからいけないので、遅延評価を導入することで、以下のように、無駄なデータ構造の生成やループ処理を排した、効率的な計算を行えるようになります。

LazyList(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

(11 :: LazyList(2,3,4).map(_ + 10)).filter(_ % 2 == 0).map(_ * 3)

LazyList(2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

(12 :: LazyList(3,4).map(_ + 10)).filter(_ % 2 == 0).map(_ * 3)

(12 :: LazyList(3,4).map(_ + 10).filter(_ % 2 == 0)).map(_ * 3)

36 :: LazyList(3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

36 :: (13 :: LazyList(4).map(_ + 10)).filter(_ % 2 == 0).map(_ * 3)

36 :: LazyList(4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

36 :: LazyList(14).filter(_ % 2 == 0).map(_ * 3)

36 :: LazyList(14).map(_ * 3)

LazyList(36,42)

行数は長くなったので今一つ効率化された感が分かりづらい気がしますが。。。

実装

TypeScript で、遅延評価される配列 LazyArray を実装していきます。
僕は普段から JavaScript を TypeScript で書いていますが、関数型なプログラムを書く場合は、 TypeScript でデータ構造をきちっと定義して書いていくメリットが特に大きいと思います。
Scala や Haskel にならって、 head :: tail という構造にします。

export interface ILazyArray<A> {
    head: A;
    tail: ILazyArray<A>;
}

ファクトリーメソッド

無限長を扱うにはどうすればよいでしょうか？
ES6 で導入された、 generator function を利用できるとよさそうです。

// 無限長のフィボナッチ配列の生成
let fibonacci = LazyArray(function*() {
    let pre = 0, cur = 1;
    for (;;) {
      let temp = pre;
      pre = cur;
      cur += temp;
      yield cur;
    }
}());

使い勝手を考えると、 native な配列からも生成可能になっていた方がよいでしょう。

let lazyArray = LazyArray([0, 1, 2]);

幸い、 native な配列も、 generator function の実行結果も、 TypeScript で {[Symbol.iterator](): IterableIterator<A>;} という型として表現できるので、 LazyArray のファクトリーメソッドは以下のように書くことができます。

export function LazyArray<A>(arg: {[Symbol.iterator](): IterableIterator<A>;}): ILazyArray<A> {
    let iterator = arg[Symbol.iterator](),
        head = iterator.next(),
        headValue = head.value;
    if (head.done) {
        if (typeof headValue === 'undefined') {
            return Empty;
        } else {
            return Empty.append(headValue);
        }
    } else {
        return new LazyArrayImpl(
            () => {
                return headValue;
            },
            () => {
                return LazyArray(iterator);
            }
        );
    }
}

class LazyArrayImpl<A> implements ILazyArray<A> {
    private _head: A;
    private headEvaluated = false;
    private _tail: ILazyArray<A>;
    private tailEvaluated = false;

    constructor(
        private getHead: () => A,
        private getTail: () => ILazyArray<A>
    ) {}

    get head(): A {
        if (!this.headEvaluated) {
            this.headEvaluated = true;
            this._head = this.getHead();
        }
        return this._head;
    }

    get tail(): ILazyArray<A> {
        if (!this.tailEvaluated) {
            this.tailEvaluated = true;
            this._tail = this.getTail();
        }
        return this._tail;
    }

    // 以下略
}

export const Empty: ILazyArray<any> = {
    // 略
}

泥臭さはありますが、 LazyArrayImpl で head, tail が遅延評価されているのがお分かりいただけると思います。

右畳み込みメソッド reduceRight と、それを利用した Collection API の実装

map や filter などの Collection API を遅延評価で実装するには、最初に遅延評価で実行される右畳み込みのメソッドを実装しておくと便利です。
なお、そもそも右畳み込みとは何ぞやという説明はここでは割愛します。

class LazyArrayImpl<A> implements ILazyArray<A> {

    // 前略

    reduceRight<B>(f: (acc: () => B, current: () => A, index: number) => B, initial: B, index = 0): B {
        let acc: B = null,
            accEvaluated = false;
        return f(
            () => {
                if (!accEvaluated) {
                    accEvaluated = true;
                    acc = (<LazyArrayImpl<A>>this.tail).reduceRight(f, initial, index + 1);
                }
                return acc;
            },
            () => {
                return this.head;
            },
            index
        );
    }

    // 後略

}

reduceRight の第一引数に渡す関数の中では、その要素までの畳み込み結果や、現在の要素の値、インデックスを利用できます。このうち、その要素までの畳み込み結果と現在の要素の値は、遅延評価（関数の中で参照した時点で初めて評価）されます。
この遅延評価の効果は、 reduceRight を利用した some の実装を見ると分かりやすいと思います。

    some(f: (a: A, index: number) => boolean): boolean {
        return this.reduceRight((acc: () => boolean, current: () => A, index: number) => {
            return f(current(), index) || acc();
        }, false);
    }

reduceRight に渡している関数の中で、 f(current(), index) が true を返せば、 acc() は実行されません。
したがってたとえば、

let containsOdd = LazyArray([0,1,2,3]).some((n: number) => { return n % 2 === 1; });

のようなコードを書いた場合、配列の 2 番目の要素 (= 1) の時点で条件が満たされるため、以降の要素に対する計算は行われません。
同様に、 reduceRight を利用した、 map, filter の実装は以下のようになります。

    map<B>(f: (a: A, index: number) => B): ILazyArray<B> {
        return this.reduceRight((acc: () => ILazyArray<B>, current: () => A, index: number) => {
            return new LazyArrayImpl(
                () => {
                    return f(current(), index);
                },
                () => {
                    return acc();
                }
            );
        }, Empty);
    }

    filter(f: (a: A, index: number) => boolean): ILazyArray<A> {
        return this.reduceRight((acc: () => ILazyArray<A>, current: () => A, index: number) => {
            if (f(current(), index)) {
                return new LazyArrayImpl(
                    () => {
                        return current();
                    },
                    () => {
                        return acc();
                    }
                );
            } else {
                return acc();
            }
        }, Empty);
    }

パフォーマンスの比較

実装した LazyArray のパフォーマンスがいかほどのものか、他の実装と比較してみました。

比較対象

• native の配列
• lodash
• Lazy.js
  • これも「遅延評価で早くなっている」ことを売りにしているライブラリ。
  • よく知らなかったが、グラフを見るととても速そうだし、 github の star も多いので、比較対象に追加。

比較方法

ある長さの配列に対して、以下の処理を実行して時間を計測する。

1. map メソッドを 1000 回繰り返す
2. take メソッドで先頭の 10 要素を取得して結果を native の配列に変換する x 1
3. take メソッドで先頭の 10 要素を取得して結果を native の配列に変換する x 100

ここまでの内容をちゃんと読んでこられた方は、この方法での比較がかなり「ずるい」ものであることを察せられると思います。
take メソッドで先頭の要素だけに絞り込むと、 LazyArray は実際にはその要素に対してしか map による計算を行わないので、早くなるのは当たり前ですが、そういうユースケースはあまり一般的ではないでしょう。
ただ、この比較は遅延評価の特性を理解していただくためのものであるとご理解いただければと思います。
なお、 3 の手順を追加したのは、 Lazy.js の実装を見たら、評価を遅延させるだけで評価結果をキャッシュしていないように見えたため、少し意地悪してみようと思ったからです。

結果

Chrome 44 で実行した結果がこちらです（3 回分の平均と標準偏差を表示）。

Implementation	Array length	Map (ms)	Take x 1 (ms)	Take x 100 (ms)	Total (ms)
Native	100	16.0 ± 2.6	0.3 ± 0.6	2.0 ± 1.0	18.3 ± 3.1
Native	10000	915.3 ± 120.8	0.0 ± 0.0	1.3 ± 0.6	916.7 ± 120.9
LazyArray	100	3.3 ± 0.6	22.7 ± 3.8	5.3 ± 2.5	31.3 ± 2.5
LazyArray	10000	0.7 ± 0.6	11.7 ± 4.0	2.7 ± 1.2	15.0 ± 4.6
Lazy.js	100	0.7 ± 0.6	41.0 ± 1.0	3562.0 ± 196.0	3603.7 ± 197.5
Lazy.js	10000	1.0 ± 0.0	51.7 ± 5.5	3529.3 ± 308.9	3582.0 ± 314.0
lodash	100	4.3 ± 0.6	0.3 ± 0.6	2.0 ± 0.0	6.7 ± 0.6
lodash	10000	53.7 ± 9.8	0.3 ± 0.6	1.7 ± 0.6	55.7 ± 9.9

考察

出来レース的なアレなので、配列の長さが長いときは、結果として LazyArray が一番早かったのは当然として、上記の結果から以下のことが考察されます。

無駄なループをなくすメリットよりも、オブジェクト生成のコストによるデメリットの方が大きい

map の実際の計算は、 native な配列や lodash では 'Map' の列で、 LazyArray や Lazy.js では 'Take x 1' の列で行われています。
Lazy 勢が実際には先頭の 10 要素しか計算していないことを考慮すると、非 Lazy 勢よりも実質的に計算が遅くなっていることがわかります。
ループの回数は減っているはずですが、たとえば LazyArray では map を一回計算するごとに LazyArrayImpl のインスタンスを生成する実装になっているため、 native な配列だけで済む場合と比べてその点が大きなコストになっていると考えられます。

lodash 速い

lodash が native の配列と比べて有意に速かったです。 native の配列の map は、もちろん map メソッドをそのまま使ったのですが、 lodash の map は以下のような実装になっています。

    /**
     * A specialized version of `_.map` for arrays without support for callback
     * shorthands.
     *
     * @private
     * @param {Array} array The array to iterate over.
     * @param {Function} iteratee The function invoked per iteration.
     * @returns {Array} Returns the new mapped array.
     */
    function arrayMap(array, iteratee) {
      var index = -1,
          length = array.length,
          result = Array(length);

      while (++index < length) {
        result[index] = iteratee(array[index], index, array);
      }
      return result;
    }

あ、 map 使うより while のループで回すほうが速いんですね。。（実行環境によるかもしれませんが）
また、 result は最初に長さを決めて初期化して、 result[index] に値を代入していますが、これも [] で初期化して result.push で要素を追加するより速いようです。

Lazy.js はやはり評価結果をキャッシュしておらず、残念

Lazy.js は、予想通り評価結果をキャッシュしていなかったので、 take x 100 のところで、 take x 1 の約 100 倍の時間がかかってしまいました。
これだと遅延評価というよりは単に都度計算するというだけなので、正直イケてないなと思います。

まとめ

• パフォーマンス的には、配列の遅延評価は残念ながらあまりメリットがなかった
• 無限配列を扱うみたいな目的なら、使えるかも
  • なお、単に無限配列を扱うだけなら、 generator function をそのまま使うという方法もあり得るが、 generator function は参照透過でないので、何らかの形でラップした方が使い勝手はよくなると思われる

その他

大事なことを書いていませんでしたが、遅延評価を導入した場合、メソッドの再帰呼び出しを末尾再帰にすることができません。
したがって、末尾再帰最適化を適用できず、 stack が overflow するリスクを抱えることになります。
たとえば Haskell では、この問題に対応するため、畳み込みメソッドとして、遅延評価するバージョンとしないバージョンをそれぞれ提供していたりしますが、今回作った LazyArray はそこまで作りこんでいません。