遅延評価と末尾再帰と余再帰 - あどけない話

遅延評価では再帰の効率はどうなるかという問題です。Real World Haskell で、末尾再帰は重要だと言った後に、遅延評価では末尾再帰なんて気にするなとちゃぶ台を返しています。ようやく haskell-cafeで答えを見つけたので、Luke Palmer さんの許可を得て訳を公開します。 Luke Palmer さんの説明 私が Haskell でプログラミングするときは、通常関数を末尾再帰にはしません。(Int や Bool など)正格な値へ畳み込む場合、末尾再帰を使うのはよいことです。しかし帰納的な遅延構造を作成する場合、関係する用語は（私の記憶が正しければ）「余再帰」(corecursion)であり(訳注：mapは再帰かつ余再帰だそうですが、専門的すぎるので普通の再帰でいいと思います)、末尾再帰とはまったく異なります。 リストに対し末尾再帰で map する関数を例として考えま

[Haaaa_N]

@miliushin [遅延評価と末尾再帰と余再帰 - あどけない話]:

[matsu_chara]

なるほど余再帰なる概念があるのか('~')

[satzz]

2009

[chuwb]

corecursion

[taketyan]

フーム #reading_rwh

[mnru]

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

[sirocco]

"関数をその関数を使って定義するのが再帰。データをそのデータを使って定義するのが余再帰です。"

[tanakaBox]

余再帰(corecursion)

[h-hirai]

余再帰(corecursion)

[kazutanaka]

coinduction, codata and corecursion

[r-west]

アキュムレータ？リストを持ち回る再帰は、リストに収める計算自体が遅延されてメモリを食うので、そんな末尾再帰ではなく、再帰計算をconsの中に入れてしまうべき……←不当に特殊化してしまってる希ガス

[tarao]

corecursion