CODEWITHSUNDEEP
referenceocamlrecord
SoftTimur
SoftTimur

Reputation: 5520

A module with a store

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.

Upvotes: 1

Views: 64

Answers (3)

ivg
ivg

Reputation: 35260

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

Upvotes: 1

Lhooq
Lhooq

Reputation: 4441

What you want to do is memoization, no ?

You could try this :

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 *)
    ... ...

  module HI = Hashtbl.Make (struct 
    type t = C of int 
    let equal = (=) 
    let hash (C x) = x
  end)

  let get_prime_factors =
    let h = Hashtbl.create 17 in
    fun x ->
      try Hashtbl.find h x 
    with
      Not_found -> let pf = calculate_prime_factors x in
                   Hashtbl.add h x pf;
                   pf
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
  ...

You could adapt it for negative integers (with exceptions, for example, which is better than options) but I hope you get the idea.

Upvotes: 2

Julien C.
Julien C.

Reputation: 329

I would do the following :

let get_prime_factors x =
  match get x  with
  | None ->
    let res = calculate_prime_factors x 
    in
    begin
      set x res ;
      res
    end
  | Some res -> res 
;;

You need a mutable data structure accessed by get and set. For instance, with a reference on a list (but you may prefer a hashtable) :

let my_storage = ref [] (* or something mutable *)

let get x = 
  if List.mem_assoc x !my_storage
  then Some (List.assoc x !my_storage)
  else None

let set x r =
  my_storage := (x,r) :: !my_storage ;;

You can also use exceptions instead of the option type (None and Some _).

Upvotes: 1

Related Questions