zapashcanon 04de879021 fix release script | 1 week ago | |
---|---|---|
src | 2 months ago | |
test | 2 months ago | |
.build.yml | 1 week ago | |
.gitignore | 2 months ago | |
CHANGES.md | 2 months ago | |
LICENSE.md | 4 months ago | |
README.md | 2 months ago | |
dune-project | 2 months ago | |
memo.opam | 2 months ago |
Memo is an OCaml library for memoïzation.
If you had a function fibo
defined like this:
let rec fibo x =
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2)
There’s many different ways to memoïze it.
The easiest one is to rewrite it like this:
let fibo = Memo.memo (fun fibo x ->
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2))
It’ll use the Hashtbl
module directly.
I’d like to thank Sylvain Conchon who taught me memoïzation and how to write this memo
function when I was his student.
equal
and hash
functionsWe provide a Make
functor. It can be useful in case you don’t want to use polymorphic equality or you are doing things like hash consing and you know how to compare or hash your type more efficiently.
let module Mem = Memo.Make(struct
type t = int
let equal = (=)
let hash = Hashtbl.hash
end)
let fibo = Mem.memo (fun fibo x ->
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2))
We provide a MakeWeak
functor. It works like the previous one, but the bindings in the memoïzation cache will be weak, allowing the garbage collector to remove them if they are not used somewhere else.
let module Mem = Memo.MakeWeak(struct
type t = int
let equal = (=)
let hash = Hashtbl.hash
end)
let fibo = Mem.memo (fun fibo x ->
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2))
I’d like to thank Jean-Christophe Filliâtre who taugh me forgetful memoïzation when I was doing research on binary decision diagram under his direction while I was a first year master student.
We provide a Fake
functor. It is useful if you want to quickly test a function you memoïzed with our Make
or MakeWeak
functor, but without memoïzing it. It’ll basically do nothing and should be equivalent to your initial non-memoïzed function.
let module Mem = Memo.Fake(struct
type t = int
let equal = (=)
let hash = Hashtbl.hash
end)
let fibo = Mem.memo (fun fibo x ->
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2))
With the Mk
functor, you can also directly provide a Cache
module, which should have the signature Hashtbl.S
. We will include your cache module and use it to define a memo
function:
let module Mem = Memo.Mk(
Hashtbl.Make(struct
type t = int
let equal = (=)
let hash = Hashtbl.hash
end)
end)
let fibo = Mem.memo (fun fibo x ->
if x < 0 then invalid_arg "fibo";
if x < 2 then x
else fibo (x - 1) + fibo (x - 2))
This example is useless and equivalent to using the Make
functor directly.
If you find a real use case for this which doesn’t need new dependencies, contact me and I’ll be happy to add a new functor to the library.
It should be useful only if you want to use another Hashtbl
implementation or things like this.
There’s a default value for the initial cache size. You can set it to the value of your choice, reset it to the default and get the current value like this:
Memo.set_initial_cache_size 1024;
Memo.reset_initial_cache_size ();
let curr_size = Memo.get_initial_cache_size ()
Note that with the current implementation of hash tables in OCaml, it’s better if you choose a power of two. You may saw some code using a prime number, it’s because some years ago it was the best thing to do as the hash tables implementation was different. Jean-Christophe Filliâtre explained this to me, thanks again ! Also keep in mind that if you use your own defined cache using the Mk
functor, it may not be the right thing to do.
See LICENSE.
See CHANGELOG.