2

Haskell の末尾再帰は、遅延が原因で問題が発生することを知っています。つまり、Haskell で末尾再帰を使用することは賢明でしょうか?

4

2 に答える 2

7

答えは、これらの大きな質問でいつものように、「場合による」です。

怠惰なスタイルでプログラミングしているときは、単純な再帰でうまくいくことがよくあります。たとえば、

 map f (x:xs) = f x : map f xs
 map _ []     = []

実際にmapは、標準ライブラリで定義されている方法です。そして、これは良いことです。末尾再帰関数は結果を生成するため、通常、適切に遅延することはできませんhead . map (+1) $ [1..]。

ただし、怠惰になりたくない場合もあります。古典的な例は、リストを合計するときのように、私たちがあまりにも怠惰で、本当に評価したいだけのサンクを構築し始めた場合です。

sum xs = someFold (+) 0 xs

引数+が厳密で連想的であるため、使用する理由はありませんfoldrがfoldl'、完全であり、末尾再帰であり、厳密に評価されるため、スペースが大幅に改善されます。'多くの末尾再帰関数では、各再帰ステップで変更されるアキュムレータがあり、foldl'末尾再帰関数が怠惰になりすぎてサンクを構築するのを防ぐ評価を強制します。

つまり、遅延プログラミングを行って遅延データ構造を作成している場合、末尾再帰はそれほど重要ではありません。しかし、厳密にプログラミングし、両方の引数で厳密な関数を使用する場合、良好なパフォーマンスを維持するには末尾再帰が非常に重要です。

于 2013-11-03T04:40:19.577 に答える
7

末尾再帰は、Haskell では厳密な言語ほど単純でも大したことでもありません。通常、代わりに、生産的な関数を作成することを目指す必要があります。たとえば、foldr多くの場合、生産的です

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

結合関数fが部分的な結果を遅延して生成できる場合、結果を消費しているものは何でもfoldr遅延して要求することもできます。典型的な例は「フォルダID」です

foldr (:) [] [1,2,3]          -- "force" it once
1 : {{ foldr (:) [] [2,3] }}

ここで、{{...}}はレイジー サンクです。これの呼び出しコンテキストfoldrが、たとえば、次の場合、head完了です

head (foldr (:) [] [1,2,3])
head (1 : {{ foldr (:) [] [2,3] }})
1

ただし、finfoldrが厳密である場合、foldr直線的に多くの呼び出しフレームを作成できます

foldr (+) 0 [1,2,3]
1 + {{ foldr (+) 0 [2,3] }}           -- we know it's one more than *something*
1 + (2 + {{ foldr (+) 0 [3] }})       -- ...
1 + (2 + (3 + {{ foldr (+) 0 [] }}))
1 + (2 + (3 + 0))                     -- and now we can begin to compute
1 + (2 + 3)
1 + 5
6

foldl'厳密な結合機能をすぐに動作させながら

foldl' f z []     = z
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

そのseqノイズがHaskellにこのように評価させる場所

foldl' (+) 0 [1,2,3]
foldl' (+) (1+0) [2,3]
foldl' (+) 1 [2,3]
foldl' (+) (1+2) [3]
foldl' (+) 3 [3]
foldl' (+) (3+3) []
foldl' (+) 6 []
6

これは、末尾再帰呼び出しによく似ています。

もう少し詳しくは wiki を参照してください。

于 2013-11-03T04:42:59.083 に答える