Concurrent Clean : reduceとtoList - lethevert is a programmer

まえに、toListがあればreduceいらないけど・・・という話を書いた。
[id:lethevert:20070802:p1]
reduceとtoListは表裏なのだけれど、効率のことを考えてみると（思考実験だけ）
reduceは、コレクションに含まれている要素に直接関数適用していくので効率よさそうに思える。それに対し、toListとfoldrの組み合わせは一度リストを作ってしまうので、オーバーヘッドがありそうに思える。
しかし、多分、現実は逆ではないか。
というのは、高階関数の呼び出しはオーバーヘッドが大きい。

foldr f [] z = z
foldr f [a:aa] z = f a (foldr f aa z)

という関数では、fには

add a b = a + b
add a = add_a
　where add_a b = a + b

という２種類の関数を与えることが許される。
そのため、foldrをコンパイルするときには、fの関数適用では、１引数ずつ適用してその都度関数オブジェクトを生成しなければならず、動的な関数ディスパッチと併せてかなりのオーバーヘッドが発生する。
そのため、Cleanでは、foldrを含む基本的な高階関数は全てマクロで定義している。また、マクロで定義しにくいケースでも、型クラスを使った上でspecial指定することで関数引数を渡すことをさける。
これを踏まえて、reduceとtoListを考えると、reduceは効率の悪い高階関数を使わざるを得ないのに対して、toListは適用すべき関数がconsに決め打ちであるため高階関数のオーバーヘッドが発生しない。さらに、toListと組み合わせるfoldrはマクロである。
Cleanは遅延評価なので、toListとfoldrを組み合わせても、中間データが大きなメモリを占めることがないため、全体としてtoList+foldrの方がreduceよりも効率よく処理を行うことができるのではないか？

- - -

という仮説をもって、toListで生成されたABCコードを眺めてみた。結果、

jmp_ap 2
jsr_ap 2

という命令があって、２引数を同時に適用している。
ところで、この命令は以前CleanJをやったときにはテストケースで作り出せなかった命令なので、ABC machine instructionsにはデータがない。

- - -

うーむ。そうでもないな。
reduceを作ってみたけれど、同じようなコードになる。
FingerTreeのケースでは、Treeが再帰的なので、toListの内部処理が高階関数化することを避けられないからかな。
だとすれば、むしろtoList+foldrになるよりも、reduceを作る方が合理的ということになる。