OCamlでのメモ帳と参照リスト

Question

私はOCamlを学んでいます。私は、OCamlが命令型プログラミングと関数型プログラミングの両方を私たちに提供していることを知っています。

私はOCamlの

次のように機能 fibonacci1は、標準的な方法で実装されている

let memoise f = 
    let table = ref [] 
    in 
    let rec find tab n = 
    match tab with 
    | []   -> 
      let v = (f n) 
      in 
      table := (n, v) :: !table; 
      v 
    | (n', v) :: t -> 
      if n' = n then v else (find t n) 
    in 
    fun n -> find !table n 

let fibonacci2 = memoise fibonacci1 

でn番目のフィボナッチ数を計算するために私のコースの一環として、このコードに出くわした：

let rec fibonacci1 n = 
    match n with 
    | 0 | 1 -> 1 
    |  _ -> (fibonacci1 (n - 1)) + (fibonacci1 (n - 2)) 

を

私の質問は、フィボナッチ2でどのようにしてメモを取っているかということです。 tableが関数fibonacci2の内部で定義されているため、関数が計算を終了した後、リストtableが失われ、各呼び出しのたびにテーブルが何度も繰り返し作成されることになります。

OCaml REPLで関数fibonacci 35を2回呼び出し、2回目の関数呼び出しでは、関数への最初の呼び出しよりも速く応答が返されました（私の予想とは逆です）。

私はrefを使用して変数を宣言すると、デフォルトでグローバルスコープになります。

だから私はこの

let f y = let x = ref 5 in y;; 
print_int !x;; 

を試してみました。しかし、これはxの値が無制限であることを言って私にエラーを与えました。

これはなぜこのように動作しますか？

Answer 1

関数memoiseは値を返します（f）。 （fは関数です）。その価値の一部はテーブルです。 memoiseに電話するたびに、別の値（別のテーブルで）を取得します。

この例では、戻り値fの名前はfibonacci2です。したがって、fibonacci2という名前のものには、その内部にテーブルfによって使用できるテーブルがあります。

デフォルトでグローバルスコープはありません。これは大きな混乱です。とにかく、これはスコープではなく生涯の問題です。 OCamlのライフタイムは、何らかの形でオブジェクトに到達できる限り、最後になります。テーブルの場合、それは返された関数を介して到達することができ、したがって、関数が実行している限り、それは続きます。

あなたの第二の例では、xの範囲（ない寿命）をテストしていると、確かにxの範囲は、そのletのsubexpresssionに制限されています。元のコードでは、tableのすべての使用はletの範囲内にあるため、問題はありません。

参考文献は少し難解ですが、OCamlの基本的なセマンティクスはラムダ計算から来ており、きれいです。そのため、OCaml（IMHO）でコーディングするのはとても喜ばしいことです。