recursion - 如何记住递归函数？

Question

考虑一个递归函数，例如由以下项定义的Euclid算法:

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)的经典方法
在此向该功能添加备注是没有用的，因为这只会节省第一次调用的时间。

我发现了有关如何在Lisp或Haskell中记住此类功能的详细信息:

How do I memoize a recursive function in Lisp?

Memoization with recursion

这些建议取决于Lisp中覆盖功能的符号定义的能力或Haskell使用的“按需调用”策略，因此在OCaml中没有用。

Answer 1

获胜的策略是定义要以连续传递样式内存的递归函数:

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函数，我们添加一个参数“continuation”来代替递归。现在，我们定义两个高阶函数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)