このフィオナッチ関数はどのように機能しますか？

Question

私がやっているFunctional Programmingコースの現在の練習課題では、特定の関数をメモしたバージョンを作る必要があります。メモ化について説明するには、次の例を与えます。

fiblist = [ fibm x | x <- [0..]] 

fibm 0 = 0 
fibm 1 = 1 
fibm n = fiblist !! (n-1) + fiblist !! (n-2) 

しかし、私はこの仕組みが完全に理解できません。

fibm 3に電話しましょう。

fibm 3 
--> fiblist !! 2 + fibList 1 
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1 
--> fibm 2 + fibm 1 
--> (fiblist !! 1 + fiblist 0) + 1 
--> ([fibm 0, fibm 1] !! 1 + [fibm 0] !! 0) + 1 
--> (fibm 1 + fibm 0) + 1 
--> 1 + 0 + 1 
--> 2 

他の質問/回答から

と私は何とか、評価さfiblistは呼び出しの間で共有されていることを学びましたグーグル。

これは、たとえばfiblist !! 2 + fiblist !! 1の場合、リストの値はのために1回だけ計算され、次にfiblist !! 1のために再計算されることを意味しますか？

次に、2つのフィボナッチ数は1回の呼び出しで1回だけ計算されるため、指数関数の呼び出し回数はありません。しかし、fiblist機能のコールの「低い」レベルはどうですか？彼らは元のfibmコールで計算されたfiblistからどのように利益を得ますか？

Answer 1

ここで重要な部分は、リストが遅延評価されていることです。つまり、要素が初めて要求されるまで計算されません。しかし、それが評価されれば、それは他に何かを探すためのものです。したがって、あなたの例では、値はのために一度だけ計算され、次にfiblist !! 1のために再計算されるということが正しいと思います。

fiblist関数の「下位レベル」も同じように機能します。最初に私がfiblist !! 1と呼ぶときは、それはちょうど1であるfibm 1を呼び出すことによって評価され、この値はリストに残ります。フィボナッチ数を上げようとするとfiblistはfibmと呼ばれ、下位の（潜在的にすでに評価されている）位置の値を検索します。fiblistです。

Answer 2

段階的に評価を進めてみましょう。現在の式の表示に加えて、fiblistの現在の評価状態をメモリに表示します。ここでは、未評価の表現（サンクと呼ばれることが多い）を表す<expr>と、現在評価中の評価されていない表現を表す>expr<とを書きます。あなたは怠惰な評価を実際に見ることができます。リストは要求された限り評価され、完了したサブコンピューティングは将来の再利用のために共有されます。 fiblistとして

Current expression      Current evaluation state of fiblist 

    fibm 3         <[ fibm x | x <- [0..] ]> 

-> (simple expansion of the definition) 

    fiblist !! (3-1) + fiblist !! (3-2)  <[ fibm x | x <- [0..] ]> 

-> ((+) has to evaluate both its arguments to make progress, let's assume 
    it starts with the left argument; (!!) traverses the list up to the given 
    element and returns the element it finds) 

    fibm 2 + fiblist !! (3-2)    <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (simple expansion of the definition) 

    (fiblist !! (2-1) + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (we again start with the first argument to (+), 
    computing the result of (!!) does not cause any 
    further evaluation of fiblist) 

    (fibm 1 + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : >fibm 1<:>fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (expanding fibm 1 returns a result immediately; 
    this concludes the computation of fibm 1, 
    and the thunk is updated with the result) 

    (1 + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (now we compute fiblist !! (2-2)) 

    (1 + fibm 0) + fiblist !! (3-2)   >fibm 0< : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (expanding fibm 0 returns 0 immediately, and the 
    corresponding thunk can be updated) 

    (1 + 0) + fiblist !! (3-2)    0 : 1 : >fibm 2< : <[fibm x | x <- [3..] ]> 

-> (we can compute the (+), yielding the result of 
    fibm 2; the corresponding thunk is updated) 

    1 + fiblist !! (3-2)      0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

-> (now the right argument of (+) has to be evaluated, but (!!) 
    will return the already evaluated list element directly) 

    1 + 1         0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

-> (arithmetic; note that as we called fibm 3 directly in the 
    beginning, instead of fiblist !! 3, the list is unaffected 
    by this final result) 

    2          0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

（しばしば「定常応用的フォーム」のCAFとも呼ばれる）グローバル定数であり、リストの部分的評価状態が持続するとfibmへの将来の呼び出しリストの既に評価要素を再利用します。リストは最終的にますます大きくなり、ますます多くのメモリを消費します。