如何记忆递归函数？

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) 添加memoization 的高阶函数的经典方法在这里是无用的,因为它只会节省第一次调用的时间.

我已经找到了有关如何在Lisp或Haskell中记忆这样的函数的细节:

• 如何在Lisp中记忆递归函数？
• 使用递归进行记忆

这些建议依赖于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实现memoization 的函数:

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函数的两个版本,第一个没有memoization,第二个有memoization:

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

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