简单的记忆

Memoization 包含缓存函数结果，以避免多次计算相同的结果。在处理执行代价高昂的计算的函数时，这非常有用。

我们可以使用简单的阶乘函数作为示例：

let factorial index =
    let rec innerLoop i acc =
        match i with
        | 0 | 1 -> acc
        | _ -> innerLoop (i - 1) (acc * i)

    innerLoop index 1

使用相同参数多次调用此函数会一次又一次地导致相同的计算。

Memoization 将帮助我们缓存因子结果并在再次传递相同参数时返回它。

这是一个简单的 memoization 实现：

// memoization takes a function as a parameter
// This function will be called every time a value is not in the cache
let memoization f =
    // The dictionary is used to store values for every parameter that has been seen
    let cache = Dictionary<_,_>()
    fun c ->
        let exist, value = cache.TryGetValue (c)
        match exist with
        | true -> 
            // Return the cached result directly, no method call
            printfn "%O -> In cache" c
            value
        | _ -> 
            // Function call is required first followed by caching the result for next call with the same parameters
            printfn "%O -> Not in cache, calling function..." c
            let value = f c
            cache.Add (c, value)
            value

memoization 函数只是将一个函数作为参数，并返回一个具有相同签名的函数。你可以在方法签名 f:('a -> 'b) -> ('a -> 'b) 中看到这个。这样你就可以像调用阶乘方法一样使用 memoization。

printfn 调用将显示当我们多次调用该函数时会发生什么; 它们可以安全地移除。

使用 memoization 很容易：

// Pass the function we want to cache as a parameter via partial application
let factorialMem = memoization factorial

// Then call the memoized function
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 4)
printfn "%i" (factorialMem 4)

// Prints
// 10 -> Not in cache, calling function...
// 3628800
// 10 -> In cache
// 3628800
// 10 -> In cache
// 3628800
// 4 -> Not in cache, calling function...
// 24
// 4 -> In cache
// 24