功能的許可副作用

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

最初，comparaison功能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是昂貴的，並且還有許多其他功能可能會不時地調用它（例如， le,ge），我想使轉換影響外部的價值。例如，我希望lt更改x0_o和x1_o的值，以便後面的函數（例如le,ge）接收可能已經轉換的參數，這會導致整個塊的計算更快。

所以我想應該使用像可變記錄的東西，任何人都可以給我一個例子嗎？另外，一般來說，這麼做是否是一個好主意（允許副作用）來優化計算？

Answer 1

我想你想要做的是memoize的（https://en.wikipedia.org/wiki/Memoization）功能Comp.convert（如果是純）：

這memoization的代碼使用哈希表來存儲結果，而不是重新計算它們（替換函數comp用一個非常簡單的代碼來測試代碼）：

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