Haskellで正格評価でループを回すには？
Haskellでは再帰的に定義された関数は遅延評価で計算される。
この遅延評価はHaskellの売りの一つであるが、これが時には仇となる。
たとえば、優雅な実装例で知られる次のフィボナッチ数の実装は遅く、メモリの消費量も多い。
fib n = fibs !! n
fibs = 1:1:zipWith (+) fib (tail fib)
これは、値が評価されるまで計算が待機してメモリが保持されつづけられることが原因だ。
これを解決するには、遅延評価ではなく正格評価で計算すれば良い。
Haskellの神話 - あどけない話
ではzipWithを正格化したzipWith’を定義して、計算を早くする例が提示されていた。
再帰でループを表現するのは、haskellならではの優雅な実装方法だけども、基本は遅延評価なので今あげた問題がついて回る。
例えば、C言語で
old=init
for (i=1; i<100; i++) {
old = new;
new = func(old);
}
みたいな計算をhaskellでやりたい場合はどうしたら良いだろうか？
例えば、
func x = 2*x
とする。
再帰関数を使った場合は、
func x = 2*x
iter n = iters !! n
iters = 1:map (*2) (iters)
といったところだろうか？
これは遅延評価され、funcが重たい計算やメモリを使う計算になるとnの増大とともに計算速度、それ以上にメモリの面で不利になる。
そこで考えたのが、次のような正格評価での計算だ。
import Data.List
func x i = 2*x
iter n = foldl' (func) 1 [0..n]
これなら、遅延評価によるメモリ消費の増大も計算速度の低下もなくなる。
この話とは直接関係ないのだが、「再帰をよく理解したら、なるべく再帰を使ってはいけません。」はなるほどと思った。Haskell勉強したては、再帰すげーってなってたけど、強すぎる力だったんだね。
プログラム言語の進歩は言語の力を弱めて行く方向にあると思う。
変な話なのですが、再帰をよく理解したら、なるべく再帰を使ってはいけません。上記の例を見ると再帰が goto 文のように思えた人がいるかもしれませんが、その直観はあたっています。再帰はいろんなことが実現できるので、読み手には理解しずらいのです。
熟達した Haskeller は、以下のような力の階層を理解しています。
再帰
foldr、foldl など
filter、take など
上が力が強く、下へ行くほど力が弱くなります。力が強いと何でもできてしまうので、コードの意図が不明瞭となり、また間違いが入り込みやすくなります。力が弱いとできることは限られるのでコードの意図は明確となり、間違いが入りにくくなります。「目的に合う一番力の弱い手段を使う」のがよいプログラムを書くための大原則です。
