Memoize a function of type () -> 'a

Question

This memoize function fails on any functions of type () -> 'a at runtime with a Null-Argument-Exception.

let memoize f =
    let cache = System.Collections.Generic.Dictionary()
    fun x ->
        if cache.ContainsKey(x) then 
            cache.[x]
        else 
            let res = f x
            cache.[x] <- res
            res

Is there a way to write a memoize function that also works for a () -> 'a ?

(My only alternative for now is using a Lazy type. calling x.Force() to get the value.)

Answer 1

The reason why the function fails is that F# represents unit () using null of type unit. The dictionary does not allow taking null values as keys and so it fails.

In your specific case, there is not much point in memoizing function of type unit -> 'a (because it is better to use lazy for this), but there are other cases where this would be an issue - for example None is also represented by null so this fails too:

let f : int option -> int = memoize (fun a -> defaultArg a 42)
f None

The easy way to fix this is to wrap the key in another data type to make sure it is never null:

type Key<'K> = K of 'K

Then you can just wrap the key with the K constructor and everything will work nicely:

let memoize f =
    let cache = System.Collections.Generic.Dictionary()
    fun x ->
        if cache.ContainsKey(K x) then 
            cache.[K x]
        else 
            let res = f x
            cache.[K x] <- res
            res