Real World Haskell 読書会
昨日、参加してきました。第3回。前回、参加申し込みし損ねたので、私は2回目。
妙に参加者が少ないなぁ? と思ったら、ICFP プログラミングコンテストとかぶってたんですね。すっかり忘れてたわ。懇親会でも半分くらいコンテストの話題で盛り上がってました。
で、以下、ページ数は原書のページ数です。今回は4章の途中、p.84 How to Think About Loops から。
の順で話がすすみました。
p.87 のコラム (?) に末尾再帰最適化 (TCO) の説明がありますが、ここで少し議論に。末尾再帰最適化は Scheme の教科書であれば必ず出てくる話題ですが、「Haskell の場合、遅延評価があるから、末尾呼び出しにしてもここでの説明はあてはまらないんだよねー」と。
えーと、ときどきそういうお話を見かけますけど、どういうことでしょう? と聞いたら、p.94 にある foldl の評価手順の説明のところで教えてもらえました。本でも p.96 Left Folds, Laziness, and Space Leaks のところで説明してます。
リストの要素の合計を求める関数を、foldl を使って Scheme で定義すると、こうなるでしょうか。
(define (sum lst) (foldl + 0 lst))
foldl の Scheme での定義は、こうだったかな? *1
(define (foldl step zero lst) (if (null? lst) zero (foldl step (step zero (car lst)) (cdr lst))))
で、sum を数値のリストに適用すると、以下のような手順で評価されます。
(sum '(1 2 3)) ;; => (foldl + 0 '(1 2 3)) ;; => (foldl + (+ 0 1) '(2 3)) ;; => (foldl + 1 '(2 3)) ;; => (foldl + (+ 1 2) '(3)) ;; => (foldl + 3 '(3)) ;; => (foldl + (+ 3 3) '()) ;; => (foldl + 6 '()) ;; => 6
foldl の再帰呼び出しは末尾呼び出しになっているので、一定量の空間しか消費しません。
これが、遅延評価がデフォルトの Haskell だと、こうなります。
foldl step zero (x:xs) = foldl step (step zero x) xs foldl _ zero [] = zero sum xs = foldl (+) 0 xs
foldl (+) 0 (1:2:3:[]) -- => foldl (+) (0 + 1) (2:3:[]) -- => foldl (+) (0 + 1 + 2) (3:[]) -- => foldl (+) (0 + 1 + 2 + 3) [] -- => (0 + 1 + 2 + 3)
と、まぁ、foldl が呼び出されるたびに、zero は加算されて大きくなっていくのではなくて、あとで評価される予定のサンクがどんどんふくれあがっていくわけですね。
前にも理解したつもりになったことがあるような気がするけど、今度こそちゃんと覚えたぞ。
んで、そこで zero を正格に評価する foldl の別バージョン foldl' が Data.List で定義されてます。定義はこう。
foldl' _ zero [] = zero foldl' step zero (x:xs) = let new = step zero x in new `seq` foldl' step new xs
ここで出てくる seq は p.108 からの Space Leaks and Strict Evaluation で説明されてます。引数の評価順序を強制する、というような理解でいいのかな? このへんのことをきちんと理解できていれば、以前にこんなもんを書く必要もなかったのかなー?
おおまかに言って、数値計算のように構造を保持する必要がない畳み込み計算は foldl' で、構造を保存しながらする畳み込みは foldr でするのが向いているということらしい。
あとは、foldl を foldr で定義する話とか、カリー化の用語が違うよね、とか。
懇親会
メモにはこんな単語が残ってます。
あと、ICFP プログラミングコンテストの話題の他に、Haskell と副作用の話で盛り上がったりしました。詳しくは Haskellには副作用がないのか？ - あどけない話
追記
副作用の話についての応答エントリ。2009-07-02
