How to compute a value on demand and cache this value in FP/F#?

Question

In C# (OOP) I can easily compute a value on demand and remember the value once computed (aka caching), e.g.

    class WorkItem {
        private Dictionary<string, object> myFields;
        private WorkItemState myState;
        // ...
        public WorkItemState State {
            get {
                if (myState == null) {
                    myState = ParseWorkItemState(myFields["State"]);
                }
            }
        }
    }

Alternatively I could also use Lazy<T>.

I could simulate the same OOP style approach in F# using classes and mutable fields or probably again the "lazy" expression but what would be a more "idiomatic FP" approach?

Answer 1

The short answer is: The same as in C#.

State

In Functional Programming (FP), you can always use the State Monad to 'simulate ' state mutation, so one option is to pass state around:

let doSomething myFields myState =
    match myState with
    | Some s -> "foo", s
    | None -> "bar", parseWorkItemState (myFields["State"])

While 'functional', one may argue whether this is really necessary.

Referential transparency

If we assume that the state you want to memoise is immutable and that the function that calculates it is referentially transparent, whether or not you memoise the value in a mutable field is of less importance.

This is, ultimately, a semi-philosophical question of what FP really is. In my view, it's about referential transparency. If you memoise a referentially transparent function with a mutable field, it remains referentially transparent.

Lazy

If you buy that argument, then, you can often use lazy computations in F#, just as you do in C#. The requirement, however, is that the memoised function is referentially transparent.

If it's not, then nothing you do will be functional.

---

Based on comments, I present the following variation of this original memoisation snippet:

let memoize (dict : System.Collections.Generic.IDictionary<_, _>) fn x =
    match dict.TryGetValue x with
    | true, v -> v
    | false, _ ->
        let v = fn (x)
        dict.Add(x,v)
        v

Instead of using a 'global' dictionary to store memoised values, it closes over a passed-in dictionary. One can create a memoised function by partially applying it:

open System.Collections.Generic
let f = memoize (Dictionary<int, int> ()) (fun n -> n*n)

The memoised function f closes over the dictionary, which goes out of scope and gets garbage-collected together with f itself.

You can pass f around, and the dictionary is along for the ride.

This fits conceptually nicely with the realisation that closures are objects, and objects are closures.