reference - 允许函数的副作用

Question

我定义了一个模块 Comp其操作成本很高。在大多数情况下，对于 Comp.t 类型的值, int 类型的值可以计算，可用于加速许多操作。所以我定义了一个类型x如下代表2种情况:1)整数已计算2)否则

type x = A of (Comp.t, int) | B of Comp.t

一个函数 convert: x -> x已编写为尝试计算 Comp.t 的整数，这个整数可能不存在，这个函数也很昂贵:

let convert (v: x): x =
  match v with
  | A _ -> v
  | B c -> 
    try to calculate the integer "i" from "c", 
    return "A (c, i)" if the integer is found; otherwise, return "B c". 

最初，比较函数 less than可以这样写:

open Comp

let lt (x0: x) (x1: x): bool =
  let x0, x1 = Comp.convert x0, Comp.convert x1 in
  match x0, x1 with
    | A (c0, i0), A (c1, i1) -> 
      i0 < i1 (* which is very fast *)
    | A (c0, _), B c1 | B c0, A (c1, _) | B c0, B c1 -> 
      Comp.lt c0 c1 (* which is quite slow *)

...
let b0 = lt x0_o x1_o in
let b1 = le x0_o x1_o in (* "le" call "convert" too *) 
let b2 = ge x0_o x1_o in (* "ge" call "convert" too *)
...

如 convert成本高，除了 lt还有很多其他功能可能会不时调用它(例如 le ， ge )，我想让转换影响外部值(value)。例如，我想要 lt更改 x0_o 的值和 x1_o ，以便稍后的函数(例如 le ， ge )接收可能已经转换的参数，这会导致整个 block 的计算速度更快。

所以我想应该使用可变记录之类的东西，谁能给我一个例子？另外，一般来说，这样做(允许副作用)来优化计算是一个好主意吗？

Answer 1

我认为你想要做的是内存( https://en.wikipedia.org/wiki/Memoization )函数 Comp.convert (如果它是纯的):

这个内存代码使​​用哈希表来存储结果而不是重新计算它们(用一个非常简单的函数替换了函数 Comp.convert 来测试代码):

let convert x = x +  3

let convert_m' () = 
  let tbl = Hashtbl.create 100 in
  (fun x -> if Hashtbl.mem tbl x then Hashtbl.find tbl x else 
      begin 
        let n = convert x in
        Hashtbl.add tbl x n;
        n 
      end
  )

let convert_m = convert_m' ()
let b = convert_m 6