16

なぜだろうか

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

スタックオーバーフローエラーは発生しません。プレリュードの++は単純で、末尾再帰ではないようです。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

編集：当初、この問題は前奏曲で++が定義されている方法、特に書き換えルールに関係していると思いました。したがって、質問は以下のように続きました。議論は私にこれが事実ではないことを示しました。遅延評価効果によってコードがスタックオーバーフローなしで実行されるようになったと思いますが、その方法はよくわかりません。

これだけで、スタックオーバーフローが発生するはずですよね？だから私はそれがおそらく++の定義に従うghc魔法と関係があると思います：

{-＃ルール "++" [〜1] forallxsys。xs ++ ys = augment（\ cn-> foldr cn xs）ys＃-}

*それはスタックオーバーフローを回避するのに役立ちますか？誰かがこのコードで何が起こっているのかについてのヒントを提供できますか？**

4

3 に答える 3

9

プレリュードの++は単純で、末尾再帰ではないように見えます...したがって、これだけで、スタックオーバーフローが発生するはずですよね？

末尾再帰ではないものは怠惰になる可能性があるため、Haskellでは末尾再帰ではない方が末尾再帰よりも優れていることがよくあります。ここにリストする定義は、末尾再帰の定義よりもはるかに優れています。末尾再帰の定義は、最初の要素のみが必要な場合でも、再帰を続けてリスト全体を生成するためです。一方、末尾再帰ではないものは、必要なだけの作業を実行します。

于 2010-05-19T23:02:57.163 に答える
8

これは、スタックを使用しないため、最適化や書き換えルールがないインタープリターでも、スタックオーバーフローは発生しません。

（++）の定義を見てください。たとえば、次のようになります。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

重要なのはx : (xs ++ ys)、つまり、（:)"cons"コンストラクターによって保護された再帰です。Haskellは怠惰であるため、cons操作にサンクを割り当て、再帰呼び出しはこの（ヒープに割り当てられた）サンクに行きます。したがって、スタック割り当てはヒープ割り当てになり、かなり拡張できます。つまり、これは大きなリストをたどり、ヒープ上に新しいconsオブジェクトを割り当てて、トラバースしているオブジェクトを置き換えるだけです。簡単！

「リバース」は少し異なります。

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

これは末尾再帰のアキュムレータスタイルの関数であるため、ここでもヒープに割り当てられます。

ご覧のとおり、関数はスタックではなくヒープでconsセルを使用することに依存しているため、スタックオーバーフローは発生しません。

これを実際に釘付けにするために、GCvmからの実行時統計を見てください。

$ time ./B +RTS -s
99

         833 MB total memory in use (13 MB lost due to fragmentation)
         Generation 0:  3054 collections,     0 parallel,  0.99s,  1.00s elapsed
         %GC time      82.2%  (85.8% elapsed)

あなたの大きなリストがあります-それはヒープに割り当てられ、私たちは時間の80％を（++）によって作成された短所ノードのクリーンアップに費やします。

レッスン：スタックをヒープと交換できることがよくあります。

于 2010-05-31T04:59:53.177 に答える
4

編集：完全に間違っていないとしても、以下の答えは完全に無関係です。遅延評価を実際に理解していることを示すドン・スチュワートは、正しい説明をしています。

を実行すると、使用されている関数がとghc -ddump-simplであることがわかります。これらの関数は、大きなリストのスタックをオーバーフローさせないように設計されています。プレリュードに表示されるのは「リファレンス実装」であり、実際にコンパイルされるコードではありません。GHC.Base.++GHC.List.reverse

これが私がGHCソースディストリビューションから掘り出したいくつかのコードです：

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

この：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)     ys
  #-}

最初のケースでは、何が起こっているのかが明確になっているはずです。第二に、私は書き換えルールについて少し曖昧です...

于 2010-05-19T22:16:14.423 に答える