如何記憶遞歸函數？

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如何工作。