Memoization
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060909 (04:10) 
From:  Andrej Bauer <Andrej.Bauer@a...> 
Subject:  Re: [Camllist] Memoization 
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 higherorder 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 