Function return value caching in F#

Posted on Tue 20 December 2011 in Coding

In my TestNess project I have decided to try to rewrite certain parts in F# to see if the code can benefit from functional programming. It is also a learning thing as I’m definitively not well versed in functional programming - yet :-). One of the specific problems I try to address is to create sub structures given a root structure. The root structure is typically a method, and a sub structure can be a call graph for that method. Creating a call graph is non-trivial, so preferably I want to do this only once for each method, and I therefore need to cache the graph.

This is in itself not a problem at all, but my colleague Jimmy told me he was pretty sure that functional languages have some sort of build-in caching in general. This lead me to investigate a bit, and I ended up on this page.

To test return value caching, I created a tiny Visual Studio 2010 project which can be fetched from GitHub.

To begin with, I need a type from which I can create instances (this type corresponds to the aforementioned call graph):

type AType(i:int) = class end

(You gotta love the conciseness!) Next, a function that creates an instance of the type given some input:

let produceWithArg i =
    new AType(i)
let produce = produceWithArg

For the sake of unit testing this, I’ll create an “alias” function called produce. I’ve created two really simple unit tests, one that verifies that the function produces the same value if given the same input repeatedly, and one that verifies that the return values are not the same for different inputs. Here they are in all their glory (I chose NUnit simply because I had it on my machine):

[<TestFixture>]
type cachingFixture() = class

    [<Test>]
    member self.cacheWithSameInputTest() =
        Assert.AreSame (produce 1, produce 1)

    [<Test>]
    member self.dontCacheWithDifferentInputsTest() =
        Assert.AreNotSame (produce 1, produce 2)

end

With the produce function as defined above, the first test fails while the second passes. This is quite expected, as the function obviously creates a new instance each time it is called.

The first attempt at a caching solution, then, is to remove the argument. According to the link mentioned previously: “When F# comes across a function with no parameters, F# will only evaluate the function once and reuse its value everytime the function is accessed.” Let’s try it:

let produceNoArg =
    fun i -> new AType(i)
let produce = produceNoArg

Unfortunately, the test result is the same as before. The reason? Well, what’s being cached in this case is indeed the return value, which happens to be the (anonymous) function! But if the returned function is called twice, it will of course create two instances of the type! It’s return value cannot be cached since it takes a parameter.

Lesson learned: This type of caching is only interesting if the evaluation of the function is expensive but the execution is trivial. My situation is directly orthogonal to this!

The next attempt is to use lazy evaluation. Using the lazy keyword, we can create a Lazy<AType> instance that caches its value:

let produceLazy i =
    lazy(new AType(i))
let produce i = (produceLazy i).Force()

Note that this is not as transparent as before; we need to call the Force() method to retrieve the value. And sadly, our tests are still in the same state - the first fails and second passes. What happened is that two Lazy<AType> were created, and they won’t cache values between each other for obvious reasons.

Would it be better to combine a parameter-less function with lazy evaluation? No, because at some point we must introduce a function that takes a parameter, and then everything is lost.

So the third attempt is to use memoization, which in this context means explicit return value caching. But we can do a bit better than having to be explicit in every function that needs caching. I use the memoize function copied from the link above like so:

let produceMem = memoize(fun i ->
    new AType(i))
let produce = produceMem

And finally both tests pass!