1

私は次の制御構造を使用しています（これは末尾再帰だと思います）

untilSuccessOrBigError :: (Eq e) => (Integer -> (Either e a)) -> Integer -> e -> (Either e a)
untilSuccessOrBigError f count bigError
  = case f count of
         Right x -> Right x
         Left e -> (if e==bigError then Left e else untilSuccessOrBigError f (count - 1) e)

反復深化を行うには

iterativeDeepening :: (a -> [a]) -> (a -> Bool) -> (a -> Bool) -> a -> Either String a
iterativeDeepening stepFunc isAValidSolution isGraphBottom x
  = untilSuccessOrBigError
        (\count -> dfsWithMaxDepth stepFunc isAValidSolution isGraphBottom count x)
        (-1)
        "Reached graph bottom"

この空きメモリは（技術的には到達できなくなるため）、各反復深化後のようになりますか？そうでない場合は、制御構造をどのように書き直す必要がありますか？

PS 2番目に、末尾再帰構造は、この場合ではなくても、前の値に追加するようにスタック上のものにアクセスできることが多いため、これは失敗するように見えます。– Roman A.Taycher11月28日12:33PPS3番目に、dfsWithMaxDepthが返されるとすぐに、dfsWithMaxDepth内の値を破棄できると思いますが、多くの回答は多くのメモリを消費しません。–ローマンA.タイチャー11月2日

4

1 に答える 1

2

一見したところ、これが適切にガベージコレクションされない理由はなく、TCOが実行されない理由もありません。

一般に、Haskellではtcoとガベージコレクションについて別の方法で考える必要があります。ここにリストされている関連する質問の多くは役立つようです。基本的に、GHCHaskellの操作的セマンティクスを怠惰なグラフ還元として想像したいと思います。

AST全体がメモリにあり、名前のすべての使用法からその定義への追加の矢印があり、「main」の値を要求するとします。これを取得するには、mainで呼び出された最初の関数の値を確認し、それを代入する必要があります。つまり、次に評価する必要があるものを追跡する必要があります。この削減により、以前は式としてポイントされていたものが計算され、それらが表す値に置き換えられていることがわかります。次に、それらの式でガベージコレクションを実行できます。一方、グラフの上部から現在評価している部分までのトレースは「スタック」です。したがって、構造を評価する場合は、その構造の「内部」を評価する必要があります。そうすると、スタックが大きくなります。

上記はずさんで手ぶれですが、直感を与えるのに役立つかもしれません。

于 2010-11-28T15:02:12.527 に答える