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

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. — Daniel, Dec 12 '13 at 16:35
You _could_ wrap `lazy`, something like this: `let memoize f = let result = lazy (f()) in fun () -> result.Value` — Daniel, Dec 12 '13 at 16:44

score 12 · Accepted Answer · answered Dec 12 '13 at 18:29

12

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

answered Dec 12 '13 at 18:29

Tomas Petricek

240,744
19
378
553

1

Shouldn't that be `Dictionary(HashIdentity.Structural)`? – Daniel Dec 12 '13 at 19:22
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 ` 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. – Gene Belitski Dec 12 '13 at 20:26
@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)` – Curt Nichols Dec 12 '13 at 22:35
@CurtNichols: Exactly to the point I've made - each function returned from `memoize` closes over own instance of `cache` having one 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. – Gene Belitski Dec 12 '13 at 22:57
@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. – Curt Nichols Dec 13 '13 at 01:02
Better yet, here's a walkthrough in the F# Interactive window: https://gist.github.com/curtnichols/7938520 – Curt Nichols Dec 13 '13 at 01:22
@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. – Gene Belitski Dec 13 '13 at 15:32

score 6 · Answer 2 · edited Feb 10 '22 at 02:02

6

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

edited Feb 10 '22 at 02:02

wegry

7,046
6
39
59

answered Dec 13 '13 at 14:02

Goswin Rothenthal

2,244
1
19
32

score 2 · Answer 3 · edited May 23 '17 at 11:45

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.

score -1 · Answer 4 · answered Aug 12 '16 at 13:27

-1

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

answered Aug 12 '16 at 13:27

Dzmitry Lahoda

939
1
13
34

1

This doesn't solve the problem posed in the question. `memoize1 (fun () -> 1) ()` fails with an `ArgumentNullException`, too, for the same reason. – kvb Aug 12 '16 at 14:51

Memoize a function of type () -> 'a

4 Answers4