Memoization of generic constrained functions in F#

Question

I'm trying to memoize a constrained generic function using what I believe is a standard memoization pattern in F#. Here is a simplified sample which summarises my failed attempt:

module Sample

open System.Collections.Generic;

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

let memoizedFunc: ('a -> string) when 'a: equality = memoize <| (fun x ->
    string x
)

The compiler complains about value restriction:

Value restriction. The value 'memoizedFunc' has been inferred to have generic type    val memoizedFunc : ('_a -> string) when '_a : equality    Either make the arguments to 'memoizedFunc' explicit or, if you do not intend for it to be generic, add a type annotation

As shown in the sample code above, I have already added exactly the suggested type annotation on memoizedFunc, but to no avail. The other suggestion, i.e. adding arguments (eta-conversion), will not achieve what I want with regards to memoization (each call to the function would result in a new function being cached).

My first question: how do I resolve this issue with value restriction? I could revert to a more explicit caching mechanism, but I'd prefer not to.

My second question relates to an alternative definition of the memoized function, where type parameters are added to the let binding explicitly as follows:

let memoizedFunc<'a when 'a: equality> : ('a -> string) when 'a: equality = memoize <| (fun x ->
    ...

I.e. the full example then becomes:

module Sample

open System.Collections.Generic;

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

let memoizedFunc<'a when 'a: equality> : ('a -> string) when 'a: equality = memoize <| (fun x ->
    string x
)

This now compiles, but does not achieve what I want: a new function is created and memoized every time I refer to memoizedFunc.

My second question: what is the significance of adding type parameters in let bindings as shown, versus omitting them? I would not have expected this to affect semantics, but rather just to aid type inference. But that seems not to be the case.

Any pointers or help with these two questions would be greatly appreciated.

Many thanks.

the 2nd version doesnt compile for me. "The declared type parameter 'a' cannot be used here since the type parameter cannot be resolved at compile time" — MrD at KookerellaLtd
let inline memoizedFunc< ^a when ^a: equality> : (^a -> string) = memoize string — MrD at KookerellaLtd
Strange that the 2nd version doesn't compile for you. It does for me, targeting .NET Core 3.1. The inline version you suggest also compiles, but it suffers from the same problem mentioned in part two of my question, i.e. we don't get memoization because each use of memoisedFunc triggers creation of a new function. I don't understand why though. — Michael Pedersen
im also targeting 3.1....for the inline version it sort of makes partial sense, I don't completely understand inlining, but I mentally see it as copy pasting the code into the client code, in which case, every time I call memoizedFunc, i'm calling memoize, which creates a new cache....try pasting the whole code with your new version of memoize into your question and I'll copy it. — MrD at KookerellaLtd
I've updated the post with the full version of the second example. — Michael Pedersen

tranquillity tranquillity · Accepted Answer · 2020-11-01T22:09:22

There is nothing wrong with your memoize function however the F# (and .Net as a whole) type system does not allow you to do what you seem to want to do. Dictionary<'T, 'U> is generic however for each instance of a Dictionary, 'T and 'U need to be concrete types. You cannot have a single Dictionary containing a wide variety of different types as keys even if they all resolve to string as values.

The way around this is to make all the keys some common type using an Interface for when the keys are in an unbounded set (obj can even be used as the supertype of everything) or Discriminated Unions when the keys are in a known set. The following code is an example of using obj as the key.

module Sample =

    open System.Collections.Generic

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

    let memoizedFunc: (obj -> string) =
        memoize (fun x ->
            printfn "Not in cache, getting string of %s" (string x)
            string x)

    memoizedFunc 1
    memoizedFunc "hello"
    memoizedFunc 1

Your second question I am no expert on. In general type annotations are only to aid the author and do not affect semantics. In code that does not compile they can change the error messages displayed sometimes. Annotations can make a funciton less generic using the when 'a: expr syntax than may be otherwise inferred by the compiler. These annotations are also required when the compiler detects constraints in generic code.

Memoization of generic constrained functions in F#

1 Answers