如何记住递归函数? [英] How to memoize recursive functions?

问题描述

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

Consider a recursive function, say the Euclid algorithm defined by:

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

(This is a simplified, very brittle definition.) How to memoize such a function? The classical approach of defining a high-order function memoize : ('a -> 'b) -> ('a -> 'b) adding memoization to the function is here useless, because it will only save time on the first call.

我在Lisp或Haskell中找到了有关如何记忆此类功能的详细信息:

I have found details on how to memoize such function in Lisp or Haskell:

• 如何在Lisp中记住递归函数?
• 通过递归进行记忆

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

这些建议依赖于Lisp中发现的覆盖功能符号定义的能力或Haskell使用的按需调用"策略，因此在OCaml中没有用.

These suggestions rely on the ability found in Lisp to overwrite the symbol definition of a function or on the "call-by-need" strategy used by Haskell, and are therefore useless in OCaml.

推荐答案

获胜的策略是定义要以延续传递样式记忆的递归函数:

The winning strategy is to define the recursive function to be memoized in a continuation passing style:

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定义为:

Instead of defining recursively the gcd_cont function, we add an argument, the "continuation" to be called in lieu of recursing. Now we define two higher-order functions, call and memo which operate on functions having a continuation argument. The first function, call is defined as:

let call f =
    let rec g x =
      f g x
    in
    g

它构建了一个功能g，该功能没有什么特别的，只不过调用了f.第二个功能memo构建实现记忆的功能g:

It builds a function g which does nothing special but calls f. The second function memo builds a function g implementing 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

这些功能具有以下签名.

These functions have the following signatures.

val call : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
val memo : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

现在，我们定义gcd函数的两个版本，第一个版本没有备注，第二个版本带有备注:

Now we define two versions of the gcd function, the first one without memoization and the second one with memoization:

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

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

这篇关于如何记住递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！