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.)

Bossism

Memoize is generally used to cache some computation on an argument where the argument is used as the lookup key. Lazy is the right tool in this case. – Incendiarism

You could wrap lazy, something like this: let memoize f = let result = lazy (f()) in fun () -> result.Value – Incendiarism

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

Teratogenic

Shouldn't that be Dictionary(HashIdentity.Structural)? – Incendiarism

Ain't it creates an own instance of cache dictionary for each function defined via call to memoize? Only because of this multiple keys K <null> may exist for unit->'a without a clash. As functions do not share the common cache, then any literal may play the role of the key and the whole arrangement effectively mimicks lazy approach. – Faythe

@Gene memoize returns a function that closes over its own instance of Dictionary. memoize's signature is f:('a -> 'b) -> ('a -> 'b) when 'a : equality so the function that it returns is 'a -> 'b It's the returned function that you use to memoize values. E.g., let m = memoize (fun x -> x + 1);; gives val m : (int -> int) – Overnice

@CurtNichols: Exactly to the point I've made - each function returned from memoize closes over own instance of cache having one <key,value> pair at most. Use of Dictionary just for persisting of one value is IMO an overkill, also the key is not needed at all, using a bool filled state indicator instead would be sufficient. – Faythe

@Gene Belitski, the dictionary is not created by the function returned, but by the original call to memoize. Typical usage: call memoize once to create memoizing function m (the dictionary is created by memoize and closed over by function m); call m multiple times and it will cache multiple entries in the dictionary. If you modify the fun x -> expression to print before returning (printfn "Cache has %d elements" cache.Count) you'll see that the dictionary does contain multiple elements--because the dictionary is created by memoize, not by the function that memoize returns. – Overnice

Better yet, here's a walkthrough in the F# Interactive window: gist.github.com/curtnichols/7938520 – Overnice

@CurtNichols: The point somehow is getting missing that the question is about specific group of functions having signature unit -> 'a, i.e. one and only one acceptable argument of type unit. Which, in turn, translates into cache having one entry at most within each function's closure. – Faythe

Answer 2

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

Bossism

Answer 3

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.

Faythe

Answer 4

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

Kodiak

This doesn't solve the problem posed in the question. memoize1 (fun () -> 1) () fails with an ArgumentNullException, too, for the same reason. – Bresee