how to memoize a function from an array of values

Question

take

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

then

let f (x:array<_>) = x.Length

then

let g = memoization f
let a = g [|1|]
let b = g [|1|]

I (obviously!) want b to be the retrieved memoized value already calculated, but it recalculated it.

ok, fair enough, with a C# head on, that makes sense, we're back to nasty objects, so how do I memoize a function that takes an array of values?

---

I notice that lists works nicely So whats so special about arrays?

Answer 1

The issue is that, by default, Dictionary uses reference equality to check whether an object is in the dictionary. This means that it will only work if you pass it the same array instance. The following gets the value from the cache:

let g = memoization f
let arr = [|1|]
let a = g arr
let b = g arr

If you want to memoize results based on the values in the array, you can use structural equality comparison instead. To do this, all you need to do is to pass HashIdentity.Structural as an argument to Dictionary. This uses an F#-library defined structural comparison that returns the same hash for arrays containing the same values:

let cache = Dictionary<_,_>(HashIdentity.Structural)

With this change, your original example will work as you wanted.