8

私が行っている関数型プログラミング コースの現在の課題では、特定の関数のメモ化されたバージョンを作成する必要があります。メモ化を説明するために、次の例を示します。

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 !! 2 + fiblist !! 1、リストの値は に対して 1 回だけ計算されfiblist !! 2、その後 で再利用されるということfiblist !! 1ですか?

次に、2 つのフィボナッチ数は呼び出しごとに 1 回だけ計算されるため、呼び出しの指数関数的な数はありません。fiblistしかし、関数内の呼び出しの「下位」レベルはどうでしょうか? fiblist元のfibm呼び出しで計算されたものからどのようなメリットがありますか?

4

2 に答える 2

5

評価を段階的に見ていきましょう。現在の式を表示するだけでなくfiblist、メモリ内の評価の現在の状態を表示します。そこで<expr>は、評価されていない式 (サンクと呼ばれることが多い)>expr<を示し、現在評価中の評価されていない式を示すために書いています。遅延評価の動作を確認できます。リストは要求された範囲でのみ評価され、完了したサブ計算は将来の再利用のために共有されます。

   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 と呼ばれることが多い) と同様fiblistに、部分的に評価されたリストの状態が持続し、今後の呼び出しでfibmリストの既に評価された要素が再利用されます。ただし、リストは最終的にますます大きくなり、より多くのメモリを消費します。

于 2013-03-21T11:06:48.630 に答える