Re: [Caml-list] Memoization

[Andrej Bauer <Andrej.Bauer@andrej.com>]

Erik de Castro Lopo wrote:
> 
> Unfortunately, the URL is dead. Does anybody have another link for
> that code or some other polymorphic memoizer?
> 

I use the code below to show my students what can be done with
higher-order functions. For a real implementation, we would have to use
something more efficient than association lists (but then you might end
up writing a polymorphic version of the Map module). Improvements are
welcome.

--------------------
(** [memo f] is a memoized version of function [f]. If [f] makes
recursive calls, those are not memoized. In this example we use simple
asociation lists. It would be better to use efficietn search trees.
Alas, ocaml Map module is not polymorphic (for a good reason?). *)

let memo f =
  let m = ref [] in
    fun x ->
      try
	List.assoc x !m
      with
	  Not_found ->
	    let y = f x in
	      m := (x, y) :: !m ;
	      y


(** [memo_rec f] is a memoized version of a recursive function [f].
The recursive function must not make calls to itself directly, but
rather via an extra "self" parameter, see example below. *)

let memo_rec f =
  let m = ref [] in
  let rec g x =
    try
      List.assoc x !m
    with
	Not_found ->
	  let y = f g x in
	    m := (x, y) :: !m ;
	    y
  in
    g

(** [memo_test f stamp renew] is a memoized version of function [f],
where [stamp] and [renew] are used to invalidate memoized values and
force them being recomputed. For example, [f] could be a function
which reads the contents of a file, [stamp] the function which returns
the file's modification time, and [renew] the function which compares
two modification times. Note that we keep storing new values in an
association list without removing old ones, so this creates a memory
leak. An intelligent implementation would, again, use efficient search
trees. *)

let memo_test f stamp renew =
  let m = ref [] in
    fun x ->
      try
	let y, s = List.assoc x !m in
	let t = stamp x in
	  if renew s t then
	    let y = f x in
	      m := (x, (y, t)) :: !m ; y
	  else
	    y
      with
	  Not_found ->
	    let y = f x in
	    let s = stamp x in
	      m := (x, (y, s)) :: !m; y


(** Example: the Fibonacci sequence, unmemoized, very inefficient. *)
let rec fib_slow = function
    0 -> 1
  | 1 -> 1
  | n -> fib_slow (n - 1) + fib_slow (n - 2)

(** Example: a memoized version of the Fibonacci sequence. *)
let fib_memo =
  let rec fib self = function
      0 -> 1
    | 1 -> 1
    | n -> self (n - 1) + self (n - 2)
  in
    memo_rec fib
--------------------