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

I just found that the last memoize function on the same website using Map instead of Dictionary works for 'a Option -> 'b and () -> 'a too:

let memoize1 f =
    let cache = ref Map.empty

    fun x ->
        match cache.Value.TryFind(x) with
        | Some res -> res
        | None ->
            let res = f x
            cache.Value <- cache.Value.Add(x, res)
            res

Answer 2

Memoization having a pure function (not just of type unit -> 'a, but any other too) as a lookup key is impossible because functions in general do not have equality comparer for the reason.

It may seem that for this specific type of function unit -> 'a it would be possible coming up with a custom equality comparer. But the only approach for implementing such comparer beyond extremes (reflection, IL, etc.) would be invoking the lookup function as f1 = f2 iff f1() = f2(), which apparently nullifies any performance improvement expected from memoization.

So, perhaps, as it was already noted, for this case optimizations should be built around lazy pattern, but not memoization one.

UPDATE: Indeed, after second look at the question all talking above about functions missing equality comparer is correct, but not applicable, because memoization happens within each function's individual cache from the closure. On the other side, for this specific kind of functions with signature unit->'a, i.e. at most single value of argument, using Dictionary with most one entry is an overkill. The following similarly stateful, but simpler implementation with just one memoized value will do:

let memoize2 f =
    let notFilled = ref true
    let cache = ref Unchecked.defaultof<'a>
    fun () ->
        if !notFilled then
            cache := f ()
            notFilled := false
        !cache

used as let foo = memoize2(fun () -> ...heavy on time and/or space calculation...) with first use foo() performing and storing the result of calculation and all successive foo() just reusing the stored value.

Answer 3

Solution with mutable dictionary and single dictionary lookup call: let memoize1 f = // printfn "Dictionary" let cache = System.Collections.Generic.Dictionary() fun x -> let result, value = cache.TryGetValue(x) match result with | true -> value | false -> // printfn "f x" let res = f x cache.Add(x, res) res