Модуль с магазином

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 ...). Это нормально для меня использовать ссылки. Но я не знаю, как автоматически запускать calculate_prime_factors, если изменяется значение удержания (то есть !vr).

Answer 1

Похоже, что вы ищете это решение:

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 

Это называется memoizing. И этот конкретный пример можно решить еще проще, с расчетами Lazy.

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

Answer 2

Я хотел бы сделать следующее:

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. Например, со ссылкой на список (но вы можете предпочесть 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 ;; 

Вы также можете использовать исключение вместо того option типа (None и Some _).

Answer 3

Что вы хотите сделать, это memoization, no?

Вы можете попробовать это:

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

Вы можете адаптировать его для отрицательных чисел (за исключением, например, что лучше, чем варианты), но я надеюсь, что вы получите эту идею.