OCaml'de Memoisation ve Bir Referans Listesi

Question

Öğreniyorum OCaml. Biliyorum ki OCaml, hem zorunlu programlama tarzı hem de işlevsel programlamayı sağlıyor. aşağıdaki gibi

Ben fonksiyonu fibonacci1 standart şekillerde uygulanmaktadır OCaml

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 

yılında n'inci Fibonacci sayı hesaplamak için benim tabii bir parçası olarak bu kodun rastladım:

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

Şimdi sorum şu: fibonacci2'de nasıl hatıralara ulaşıyoruz. Fibonacci2 fonksiyonu içinde table tanımlanmıştır ve bu nedenle, mantığım, fonksiyonun hesaplaması bittikten sonra table listesinin kaybolması gerektiğini ve her aramadan sonra tablonun tekrar tekrar üretileceğini belirtir.

OCaml REPL'de iki kez fibonacci 35 işlevini çağırdığım basit bir sınama çalıştım ve ikinci işlev çağrısı, yanıtı işlevimin ilk çağrısından (beklentilerimin aksine) önemli ölçüde daha hızlı döndürdü.

ref kullanarak bir değişken bildirmek, varsayılan olarak genel bir kapsam verirse bu mümkün olabilir.

Yani bu

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

çalıştı Ama bu bana x'in değeri sınırsız olduğunu belirten bir hata verdi.

Bu neden böyle davranıyor?

Answer 1

memoise işlevi bir değer döndürür, f olarak adlandırın. (f bir işlev olarak gerçekleşir). Bu değerin bir kısmı tablo. memoise numaralı telefonu her aradığınızda farklı bir değer elde edeceksiniz (farklı bir tablo ile).

Örnekte, f döndürülen değeri fibonacci2 adı verilir. Yani, fibonacci2 adlı şeyin içinde f işlevi tarafından kullanılabilecek bir tablo vardır.

Varsayılan olarak genel bir kapsam yoktur, bu büyük bir karmaşa olacaktır. Her halükarda, bu kapsam değil, ömür boyu bir sorudur. OCaml'daki yaşamlar, bir nesneye bir şekilde ulaşılabildiği sürece devam eder. Tabloda, döndürülen işlev aracılığıyla ulaşılabilir ve bu nedenle işlev kadar devam eder. İkinci örnekte

Eğer x kapsamını (değil süresi) test edilir, ve gerçekten de x kapsamı onun let arasında subexpresssion ile sınırlandırılmıştır. (Yani, sadece kullanılmayan y ifadesinde anlamlıdır.) Orijinal kodda, table'un tüm kullanımları let'un içinde olduğundan sorun yoktur. Referanslar biraz zor olsa da, OCaml'ın altta yatan semantiği lambda matematiğinden gelir ve son derece temizdir. İşte bu yüzden OCaml'da (IMHO) kod yazmak çok zevkli.