缓存函数结果f#

Question

例如，我有一个对其参数恒定的函数

let is_prime x = (test)

但是它很大而且很慢。所以我希望它的结果只计算一次，而我可以根据需要多次调用它。

我尝试以非函数式语言的方式来做到这一点：

let _is_prime x = (test)

let mutable _is_prime_primes = []
let mutable _is_prime_tested = []

let is_prime x =
    if List.exists (fun el -> el = x) _is_prime_primes then
        true
    else
        if List.exists (fun el -> el = x) _is_prime_tested then
        false
    else 
        let result = _is_prime x
        if result then _is_prime_primes <- x :: _is_prime_primes
        _is_prime_tested <- x :: _is_prime_tested
        result

但我认为我“大错特错”了。对于函数式语言来说，缓存这样的结果一定是非常常见和简单的事情。

Answer 1

互联网档案馆

链接。

Answer 2

let cache f =
    let dict = new Dictionary<_,_>()
    fun n ->
        if dict.ContainsKey(n) then dict.[n]
        else
            let r = f n
            dict.[n] <- r
            r

它的签名是

('a->'b) -> ('a->'b) when 'a : equality

。 它采用非柯里化函数并返回另一个具有相同签名的函数。 对于传递给它的每个唯一参数，给定的函数仅调用一次。 这使得它非常适合昂贵的纯函数。 然而，这个缓存函数不是纯粹的，也不是线程安全的。 这是其用法的示例：

let slow n = // 'a -> 'a
    System.Threading.Thread.Sleep(1000)
    n

let fast = cache slow // 'a -> 'a

调用 

fast 1

第一次调用时会导致一秒钟的睡眠。 每次使用相同参数的连续调用都会立即返回该值。

Answer 3

let cache f =
    let mutable dict = Map.empty<_, _>

    fun n ->
        dict
        |> Map.tryFind n
        |> function
            | Some v -> v
            | None ->
                let r = f n
                dict <- dict |> Map.add n r
                r