あどけない話スマートフォン用の表示で見るあどけない話インターネットに関する技術的な話など2009-11-22遅延評価と末尾再帰と余再帰Haskell遅延評価では再帰の効率はどうなるかという問題です。末尾再帰は重要だと言った後に、遅延評価では末尾再帰なんて気にするなとちゃぶ台を返しています。さんの許可を得て訳を公開します。プログラミングするときは、通常関数を末尾再帰にはしません。)正格な値へ畳み込む場合、末尾再帰を使うのはよいことです。帰納的な遅延構造を作成する場合、関係する用語は(私の記憶が正しければ)「余再帰」(corecursion)であり(訳注:mapは再帰かつ余再帰だそうですが、専門的すぎるので普通の再帰でいいと思います)、末尾再帰とはまったく異なります。する関数を例として考えましょう。[1,2,3]は、他のすべてのことより先に、次のように畳み込みます。3]もし、末尾再帰がスタック領域を節約するのであれば、逆にヒープ領域を消費してしまうでしょう。使うと、二乗のコストがかかります。コストは、左の引数の長さに比例するからです。中にあることが分かりますか?新しい構造は、引数として渡されるのではなく、再帰の外で構築されていきます。言い換えれば、入力の全体を見なくとも、いくつかの出力を生成することが可能です。これは、よい性質です。いう記号を使ったのは、リストの先頭をもう忘れてしまってもよいことを強調するためです。リストの残りを処理して行くだけでよいのです。そこで、リストの先頭は回収可能です。空間コストは一定です。命令型言語か正格関数型言語(つまり他のほとんどの言語)に慣れているのであれば、こつを掴むのに時間がかかるでしょう。23:19遅延評価と末尾再帰と余再帰Tweet広告を非表示にする関連記事2019-02-15さようなら遅延評価Haskellがとっつきにくい原因の一つに遅延評価がある。山本和彦id:kazu-yamamoto子育て真っ最中のHaskeller。Haskell月別アーカイブはてなブログをはじめよう!kazu-yamamotoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。