haskell - GHCはいつ共有を使用しますか？

Question

初心者の質問。私は次のことについて少し混乱しています：GHC（Haskell？）の遅延評価方法には共有の使用が含まれていることを読みました。たとえば、式を評価します。

(1+1)*(1+1)

一度だけ計算1+1します。GrahamHuttonの著書「ProgramminginHaskell」では、これは、両方の発生1+1を1つのコピーへのポインタに置き換え、その1つのコピーだけを評価することによって実現されると説明されています。

しかし、によってn番目のフィボナッチ数を計算するにはnfib n = if (n<2) then n else fib (n-1) + fib(n-2)で指数関数的な時間がかかります。上記を理解していないと、たとえば次のfib 5ように評価されることがわかります。

fib 5 => fib 4 + fib 3 => fib 3 + fib 2 + fib 3 => x + fib 2 + x

とx = fib 3 = fib 2 + fib 1 = y + fib 1

それでfib 5 = y + fib 1 + y + y + fib 1

とy = fib 2 = fib 1 + fib 0 = 1

それでfib 5 = 1 + 1 + 1 + 1 + 1

ここでx、およびyは共有値として導入されました。

fib kしかし、この手順は、の反復生成の標準的な方法よりもいくらか効率が劣りますが2<=k<=n、実際に関数を評価するほど長い実行時間にはならないことは明らかです。それで、私の理解の何が問題になっていますか？

Answer 1

GHCでの共通部分式除去に依存することはできません（技術的な理由から、遅延値を共有するとスペースリークが発生する可能性があるため）。

経験則として、値は名前で共有されます。したがって、次のように部分式に名前を付けます。

 n * n
    where n = 1 + 1

そしてあなたは共有を保証します。

単純な例では、GHCはコンパイル時にすべてを計算するだけであることに注意してください。上記の説明は、実際には「ビッグ」データにのみ適用されます。

バキュームなどのデバッグツールを使用して共有を監視できます。このような共有値は、複数の参照を持つヒープ割り当てオブジェクトとして表されます。