[解決済み] このフィボナッチ関数はどのようにメモされているのですか？

質問

このフィボナッチ関数はどのようなメカニズムでメモされているのでしょうか？

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

それに関連して、このバージョンはなぜか？

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

どのように解決するのですか？

Haskellの評価機構は バイニードル であり、ある値が必要とされたときにそれを計算し、再び要求されたときのために用意しておく。もし、あるリストを定義すると xs=[0..] というリストを定義し、後でその 100 番目の要素を要求するとします。 xs!!99 を指定すると、リストの 100 番目のスロットは "fleshed" となり、数字である 99 を保持し、次のアクセスに備えます。

これがあのトリック、"going-through-a-list" を利用しているところです。通常の二重回帰フィボナッチ定義では fib n = fib (n-1) + fib (n-2) というように、関数自体が上から2回呼び出されるため、指数関数的な爆発が起こります。しかし、このトリックでは、中間結果を表すリストを作成し、そのリストを通過していくのです。

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

このトリックは、リストを作成すること、および fib . これを実現する最も簡単な方法は という名前にすることです。 というリストを作成することです。 "あなたがそれに名前を付けるなら、それはとどまるでしょう."。

最初のバージョンは単相定数を定義し、2番目はポリモーフィック関数を定義しています。多相関数は異なる型のために同じ内部リストを使用することができません。 共有できない つまり、メモ化はできません。

最初のバージョンでは、コンパイラは 寛大 で、定数部分式 ( map fib' [0..] ) を取り出して、それを別の共有可能なエンティティにするのですが、そうする義務があるわけではありません。 ^{というケースも実際にありますし、私たちが しない を自動的に実行してほしい場合があります。}

( を編集してください。 ) これらの書き直しを検討します。

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

ということで、本当のところはネストされたスコープ定義についてだと思われます。1番目の定義では外部スコープがなく、3番目の定義では外部スコープを呼び出さないように注意しています。 fib3 を呼び出すのではなく、同じレベルの f .

の新しい呼び出しは、それぞれ fib2 を呼び出すと、そのネストされた定義が新たに作成されるようですが、これはそれらのいずれかが は は (理論的には) 異なる定義が可能だからです。 によって の値に応じて n の値に依存します (この点を指摘してくれた Vitus と Tikhon に感謝します)。最初の定義では n への依存はなく、3番目の定義では依存はありますが、それぞれ個別の fib3 への呼び出しは f の呼び出しは、同じレベルのスコープから、この特定の呼び出しの内部の定義のみを呼び出すように注意されています。 fib3 であるため、同じ xs の呼び出しに再利用(つまり共有)されることになります。 fib3 .

しかし、上記のどのバージョンでも、コンパイラが内部定義が実際には 独立した であることを認識することはできません。 n バインディングを実行するために ラムダリフティング を実行し、その結果完全なメモ化が行われます（多相定義を除く）。実際、単相型を宣言し、-O2 フラグを付けてコンパイルした場合、3 つのバージョンすべてでまさにこの現象が起こります。ポリモーフィックな型宣言で fib3 はローカルに共有され fib2 は全く共有しない。

最終的には、コンパイラ、使用するコンパイラの最適化、テスト方法（GHCIでのファイルの読み込み、コンパイルの有無、-O2の有無、スタンドアロン）、単相型か多相型かによって、動作は全く変わるかもしれません - ローカル（呼び出しごと）共有（つまり呼び出しごとに線形時間）、メモ化（つまり最初の呼び出しで線形時間、同じか小さい引数の次の呼び出しで0時間）、または共有なし（指数時間）を示すかもしれません。

短い答えは、それはコンパイラのものです。）