小编Adè*_*Sec的帖子

让我们考虑Continuation monad的以下实现,对于CPS样式的计算产生和整数:

module Cont : sig
  type 'a t = ('a -> int) -> int
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val callCC: (('a -> 'b t) -> 'a t) -> 'a t
end = struct
  type 'a t = ('a -> int) -> int

  let return x =
    fun cont -> cont x

  let bind m f =
    fun cont -> m (fun x -> …

考虑一个递归函数,比如由以下定义的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中无用.