Как запоминать рекурсивные функции?

Question

Рассмотрит рекурсивную функцию, скажем, алгоритм Евклида определяется по формуле:

let rec gcd a b = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else gcd b r 

(. Это упрощенное, очень хрупкое определение) Как memoize такой функции? Классический подход к определению функции высокого порядка memoize : ('a -> 'b) -> ('a -> 'b) Добавление memoization к функции здесь бесполезно, потому что это только сэкономит время при первом вызове.

Я нашел подробности о том, как memoize такую ​​функцию в Лиспе или Haskell:

• How do I memoize a recursive function in Lisp?
• Memoization with recursion

Эти предложения основаны на способности найти в Лиспе перезаписать определение символа функции или стратегии «по требованию», используемой Haskell, и поэтому бесполезны в OCaml.

Answer 1

Выигрышная стратегия заключается в определении рекурсивной функции, которая будет memoized в продолжении прохождения стиле:

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else k (b,r) 

Вместо определения рекурсивна функции gcd_cont, мы добавим аргумент, «продолжение» быть называемый вместо рекурсии. Теперь мы определяем две функции более высокого порядка: call и memo, которые работают с функциями, имеющими аргумент продолжения. Первая функция, call определяется как:

let call f = 
    let rec g x = 
     f g x 
    in 
    g 

Он строит функцию g, которая не делает ничего особенного, но называет f. Вторая функция memo строит функции g реализующий мемоизации:

let memo f = 
    let table = ref [] in 
    let compute k x = 
     let y = f k x in 
     table := (x,y) :: !table; y 
    in 
    let rec g x = 
     try List.assoc x !table 
     with Not_found -> compute g x 
    in 
    g 

Эти функции имеют следующие подписи.

val call : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 
val memo : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 

Теперь определит две версии функции gcd, первый без запоминания и второй один с запоминанием:

let gcd_call a b = 
    call gcd_cont (a,b) 

let gcd_memo a b = 
    memo gcd_cont (a,b) 

Answer 2

# let memoize f = 
    let table = Hashtbl.Poly.create() in 
    (fun x -> 
     match Hashtbl.find table x with 
     | Some y -> y 
     | None -> 
     let y = f x in 
     Hashtbl.add_exn table ~key:x ~data:y; 
     y 
    );; 
val memoize : ('a -> 'b) -> 'a -> 'b = <fun> 


# let memo_rec f_norec x = 
    let fref = ref (fun _ -> assert false) in 
    let f = memoize (fun x -> f_norec !fref x) in 
    fref := f; 
    f x 
    ;; 
val memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> 

Вы должны прочитать раздел здесь: https://realworldocaml.org/v1/en/html/imperative-programming-1.html#memoization-and-dynamic-programming в книге Real World OCaml.

Это поможет вам по-настоящему понять, как работает memo.