Programowanie funkcyjne/Techniki uleniwiania i spamiętywania

Technika spamiętywania

[UWAGA: Uniwersalny spamiętywacz wymaga odwołania się do operatora punktu stałego. PRZEROBIĆ! ....]

Schemat spamiętywania jest dosyć uniwersalny: W implementacji rekurencyjnej, ilekroć chcemy wywołać rekurencyjnie procedurę rozwiązującą podproblem, sprawdzamy, czy już takie wywołanie nie miało miejsca, a jeżeli tak, to pobieramy obliczony wcześniej wynik. Możemy zaimplementować coś w rodzaju "otoczki", która filtruje wywołania procedur.

Rozważmy najpierw prosty przypadek, procedurę obliczającą liczby Fibonacciego.

let rec fib n = 
  if n <= 1 then 
    n 
  else 
    fib (n-1) + fib (n-2);;
      

Procedura memoize dodaje do procedury będącej jej argumentemmechanizm spamiętywania.

let memoize f = 
  let tab = ref empty_map
  in function x -> 
    if dom !tab x then 
      apply !tab x 
    else
      let wynik = f x 
      in begin
        tab := update !tab x wynik;
        wynik
      end;;
      

Chcąc dodać spamiętywanie do rekurencyjnej definicji procedury fib piszemy:

let rec fib = 
  memoize (function n -> 
    if n <= 1 then 
      n 
    else 
      fib (n-1) + fib (n-2)
  );;