如何记忆递归函数？

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的这样的功能？定义高阶函数的经典方法在函数中添加记忆是没有用的，因为它只会节省第一次调用的时间。

我已经找到了如何在Lisp或哈斯克尔memoize的这种功能的详细信息：

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

这些建议依靠Lisp中发现覆盖符号定义的能力函数或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真实世界OCaml。

这将帮助您真正了解memo如何工作。