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文字確保できた時点で評価を終了します。 末尾再帰になると途中の結果が分からないので、最後まで計算する・・・と、言うことなのでしょう。多分。

そんな感じで末尾再帰と遅延評価はあまり相性がよくないっぽい。 と言うか、末尾再帰すると遅延評価の恩恵を受けられない、といった方が正しいかな？