带有商店的模块

Question

从一个值计算属性的成本很高的情况经常发生。所以最好能够在计算后存储属性。我想知道如何正确编码。

我们举个例子。假设我们有一个整数类型，并且我们经常需要计算这种类型的值的质因数（假设负整数的质因数是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
  ...

目前，get_prime_factors只是调用calculate_prime_factors，因此pf_1、pf_2、pf_3的所有计算都是耗时的.我想有一种机制可以在模块内部存储质因数，这样只要整数不变，get_prime_factors 的第二次和第三次就只读取已存储的内容。

有谁知道如何修改模块 I 来实现这个？

我们可能需要引用来使这种机制成为可能（例如，let vr = ref (I.C 100) in ...）。我可以使用参考资料。但是我不知道如何在保持值（即!vr）发生变化时自动触发calculate_prime_factors。

Answer 1

我会做以下事情：

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 
;;

您需要一个由 get 和 set 访问的可变数据结构。例如，在列表中引用（但你可能更喜欢哈希表）：

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 ;;

您也可以使用异常来代替 option 类型（None 和 Some _）。

Answer 2

你想做的是memoization，不是吗？

你可以试试这个：

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

您可以将其调整为负整数（例如，有例外，这比选项更好），但我希望您能理解。

Answer 3

看起来，您正在寻找这个解决方案：

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

这叫做记忆。通过 Lazy 计算，可以更轻松地解决这个特定示例。

  module I = struct
    type t = int Lazy.t  
    let create c = lazy (do_calculate c)
    let calculate_prime_factors = Lazy.force
  end

带有商店的模块

A module with a store

ocaml

reference

record