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

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

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

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

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

Эти предложения основаны на способности Lisp перезаписывать определение символа функции или на стратегии "вызов по необходимости", используемой Haskell, и поэтому бесполезны в OCaml.
2 7
recursion memoization ocaml

2 ответа:

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

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)
5
# 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 в книге реальный мир OCaml .

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