#### memo

Memo is an OCaml library for memoïzation.

### Usage

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.

#### Simple memoïzation

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.

#### Using you own type, `equal`

and `hash`

functions

We 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))
```

#### Forgetful memoïzation

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.

#### Fake memoïzation

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))
```

#### Using your own defined cache

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.

#### Tuning

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.

### Build

To build the library:

```
scripts/build.sh
```

To clean after building:

```
scripts/clean.sh
```

### Documentation

To build the documentation:

```
scripts/doc.sh
```

You can open it in your browser using:

```
scripts/view_doc.sh
```

### Tests

To run the tests:

```
scripts/test.sh
```

To run the tests with coverage report:

```
scripts/coverage.sh
```

You can open the tests coverage report in your web browser using:

```
scripts/view_coverage.sh
```

### Format

You can format the code using:

```
scripts/format.sh
```

### License

See LICENSE.

### Changelog

See CHANGELOG.

sha256=f8f614e8b20b6b013ac02d8b7feb6038d93c6e1a41168c6c6c042b66072bcd37

sha512=5002fb536062464eccdc05d281469f0cebcb64429f07b7241bca9f56a18c40e5c7b279a55b77a6a1f1793d3d72f89f7a906c920c514d049553e12ae606d69e1d