BlankTar

about | blog | works | photo

Haskellのサンプルソースを見ていると、あんまり末尾再帰を使っている例を見ないんですよね。
schemeとかだと割とよく見るんだけどねぇ。
なぜなのかちょっと考えてみた。

テスト用の関数として、与えられた文字列のリストをスペースで繋ぐ関数joinを考えます。
この間数でalice bob charlieの三つを繋いで、先頭の8文字だけを取り出して表示すると言う操作を行います。
結果的に期待する出力は
"alice bo"
って感じ。

まずは普通の再起で書いてみる。
import Debug.Trace

join [x]    = trace (show [x]) x
join (x:xs) = trace (show (x:xs)) $ x ++ " " ++ (join xs)

main = print $ take 8 $ join ["alice", "bob", "charlie"]
とても工夫が無い。

そんでもって今度は末尾再起。
import Debug.Trace

join [x] = trace (show [x]) x
join (x:y:zs) = trace (show (x:y:zs)) (join ((x ++ " " ++ y): zs))
リストの先頭に繋いだ結果を入れて畳み込んでいこうという感じ。
何か若干面倒くさい。まあよしとしよう。

んでもって、普通の再起で実行した結果がこちら。
["alice","bob","charlie"]
["bob","charlie"]
"alice bo"
charlieが評価されてません。すごい。

末尾再帰だと
["alice","bob","charlie"]
["alice bob","charlie"]
["alice bob charlie"]
"alice bo"
だんだん繋がっていく感じがわかりやすい。
この場合だとcharlieも評価されています。

と言う訳でまあ、そういう訳です。
Haskellは遅延評価が行われるので、8文字目まで欲しいなら8文字確保できた時点で評価を終了します。
末尾再帰になると途中の結果が分からないので、最後まで計算する・・・と、言うことなのでしょう。多分。

そんな感じで末尾再帰と遅延評価はあまり相性がよくないっぽい。
と言うか、末尾再帰すると遅延評価の恩恵を受けられない、といった方が正しいかな?
< Haskellでエラトステネスの篩 Google Analytics見たらsocial-buttons.comとやらからスパムアクセスが。 >