While searching Google for info about memoization I found this
Slashdot post:
http://developers.slashdot.org/comments.pl?sid=142494&cid=11942528
which states:
I simply Googled for "memoization Ocaml" and found that code:
http://www.emeraldtiger.net/modules.php?op= modload &name=News&file=article&sid=9
The author pointed out how "sweet" polymorphism is... one block
of code that can be used to memoize any function.
Unfortunately, the URL is dead. Does anybody have another link for
that code or some other polymorphic memoizer?
Cheers,
Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo
+-----------------------------------------------------------+
"It is forbidden for a Muslim to be a loyal friend to someone who does
not believe in God and His Prophet, or someone who fights the religion
of Islam." -- Fifth grade text book from Saudi Arabia
http://www.washingtonpost.com/wp-dyn/content/article/2006/05/19/AR2006051901769_pf.html
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
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
--------------------
> 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.
Thanks Andrej, thats interesting. Is there any reason you didn't
use a Hashtbl instead of the association list? I don't really think
the the ordering of the Map module is needed.
The particular function I'm trying to memoize is a function of
two integers. I was hoping it might be possible to write a
memoize function that memoizes any function of a small arbitrary
number of parameters. Thinking about it some more I'm beginning
to this this is not possible.
Cheers,
Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo
+-----------------------------------------------------------+
Saying Python is easier than C++ is like saying that turning a
light switch on or off is easier than operating a nuclear reactor.
It is not very costly to give multiple parameters as a tuple. I think
I remember reading that the native code compiler can do this without a
heap allocation. -Mike
On Sep 8, 2006, at 6:33 PM, Erik de Castro Lopo wrote:
> Unfortunately, the URL is dead. Does anybody have another link for
> that code or some other polymorphic memoizer?
You may want to take a look at this paper by Bruce McAdam that uses a
fix-point combinator to create all sorts of wrappers for functions,
including memoization. The examples ore in SML, but translate pretty
easily to OCaml.
http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/
William D. Neumann
"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."
--Superstar Billy Graham
Hope this helps: A very simple memoization (not written by me) is
(* [memo f] creates a memoized version of a single parameter function [f] *)
val memo : ('a -> 'b) -> ('a -> 'b)
let memo f =
let h = Hashtbl.create 11 in
fun x -> try
Hashtbl.find h x
with Not_found ->
let r = f x in ( Hashtbl.add h x r; r )
This can be extended to function of two parameters as follows:
let memo2 f = curry ( memo ( uncurry f ) )
let uncurry f (x,y) = f x y
let curry f x y = f (x,y)
I further implemented a memoization system for my application based on
hash tables which also allows selective forgetting of cached values if
the memory is short. Let me know if you need it.
Jan
--
-------------------------------------------------------------------------
Jan Kybic <ky...@fel.cvut.cz> tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic ICQ 200569450
http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf
is a low-impact buildup to memoization as a monadic library.
Walid.
|!DSPAM:4503307f144882042218820!