It happens quite often that it is costly to calculate a property from a value. So it would be better to be able to store the property once it is calculated. I am wondering how to code this properly.
Let's take an example. Assume we have a type integer, and very often we need to calculate prime factors of a value of such type (let's assume the prime factors of a negative integer is None):
module I =
struct
type t = C of int
type pf = (int list) option
let calculate_prime_factors (x: t) : pf =
(* a costly function to calculate prime factors *)
... ...
let get_prime_factors (x: t) : pf =
calculate_prime_factors x
end
let () =
let v = I.C 100 in
let pf_1 = I.get_prime_factors v in
let pf_2 = I.get_prime_factors v in
let pf_3 = I.get_prime_factors v in
...
At the moment, get_prime_factors just calls calculate_prime_factors, as a consequence, all the calculations of pf_1, pf_2, pf_3 are time consuming. I would like to have a mechanism to enable storing prime factors inside the module, so that as long as the integer does not change, the second and third times of get_prime_factors just read what have been stored.
Does anyone know how to modify the module I to achieve this?
It is possible that we need references to make this mechanism possible (eg, let vr = ref (I.C 100) in ...). It is OK for me to use references. But I don't know how to trigger automatically calculate_prime_factors if the hold value (ie, !vr) is changed.
Looks like, that you're looking for this solution:
module I = struct
type t = {
c : int;
mutable result : int option;
}
let create c = {c; result = None}
let calculate_prime_factors t = match t.result with
| Some r -> r
| None ->
let r = do_calculate t.c in
t.result <- Some r;
r
end
This is called memoizing. And this particular example can be solved even easier, with Lazy computations.
module I = struct
type t = int Lazy.t
let create c = lazy (do_calculate c)
let calculate_prime_factors = Lazy.force
end