遅延評価と末尾再帰と余再帰

遅延評価では再帰の効率はどうなるかという問題です。Real World Haskell で、末尾再帰は重要だと言った後に、遅延評価では末尾再帰なんて気にするなとちゃぶ台を返しています。ようやく haskell-cafeで答えを見つけたので、Luke Palmer さんの許可を得て訳を公開します。

Luke Palmer さんの説明

私が Haskell でプログラミングするときは、通常関数を末尾再帰にはしません。(Int や Bool など)正格な値へ畳み込む場合、末尾再帰を使うのはよいことです。しかし帰納的な遅延構造を作成する場合、関係する用語は（私の記憶が正しければ）「余再帰」(corecursion)であり(訳注：mapは再帰かつ余再帰だそうですが、専門的すぎるので普通の再帰でいいと思います)、末尾再帰とはまったく異なります。

リストに対し末尾再帰で map する関数を例として考えましょう。

map f = go []
    where
    go accum [] = accum
    go accum (x:xs) = go (accum ++ [f x]) xs

map f [1,2,3]は、他のすべてのことより先に、次のように畳み込みます。

map f [1,2,3]
go [] [1,2,3]
go ([] ++ [f 1]) [2,3]
go (([] ++ [f 1]) ++ [f 2]) [3]
go ((([] ++ [f 1]) ++ [f 2]) ++ [f 3]) []
(([] ++ [f 1]) ++ [f 2]) ++ [f 3]

もし、末尾再帰がスタック領域を節約するのであれば、逆にヒープ領域を消費してしまうでしょう。（加えて、このように ++ を使うと、二乗のコストがかかります。なぜなら、++ のコストは、左の引数の長さに比例するからです。）

余再帰(訳注：普通の再帰)で map を書くのは、よく見かける例です：

map f (x:xs) = f x : map f xs

再帰呼び出しが、(:) の中にあることが分かりますか？新しい構造は、引数として渡されるのではなく、再帰の外で構築されていきます。言い換えれば、入力の全体を見なくとも、いくつかの出力を生成することが可能です。これは、よい性質です。

map f [1,2,3]
f 1 : map f [2,3]   -- そして、リストの残りの評価に取りかかるときに
... : f 2 : map f [3]  -- 上に同じ
... : f 3 : map f []  -- 上に同じ
... : []

... という記号を使ったのは、リストの先頭をもう忘れてしまってもよいことを強調するためです。リストの残りを処理して行くだけでよいのです。そこで、リストの先頭は回収可能です。この意味において、map の空間コストは一定です。

余再帰を巧みに使ったプログラミングは、Haskell の楽しみの一つです。しかし、もし命令型言語か正格関数型言語（つまり他のほとんどの言語）に慣れているのであれば、こつを掴むのに時間がかかるでしょう。

まとめ

• 正格データを生成するには末尾再帰
• 遅延データを生成するには普通の再帰