What is Memoization?
Just a simple demo outlining how you might write a simple generic callsite cache in F# aka Memoize. This is something that you can find elsewhere on the web – it’s easy to write one. What I really want to illustrate is if you were to write something similar in C# how much more boilerplate it would be. I’ve actually written a more fully-featured cache Call Handler for Unity which works with any number of arguments, but trust me when I say that it was a fair amount of work to do. And when you’re working with mutable data structures it’s difficult to know what you can do with them with regards to e.g. putting them in hash tables etc. etc. (as hash values on mutable objects can potentially change over time, but not so with immutable structures).
Memoize in C#
Anyway… here’s an example in C# of a higher-order function that takes in a given function and will wrap the call in a cache, and first some sample calling code to show how we consume it.
Ouch! This isn’t the most readable code in the world (although I tried my best :-)) On the client, we need to explicitly supply the generic type arguments so that the Memoize function knows what type of cache to create. I had hoped that the compiler could infer this based on the signature of the method being supplied, but sadly not. Also, because the cache we’re using just works on a single argument, we have to supply all values as a single Tuple, so rather than just calling Add(5,10), we have to call Add(Tuple.Create(5,10)). This isn’t great. We could try to change the way the cache works to take in multiple arguments, but there would be limitations and it wouldn’t be truly generic.
The implementation of the cache isn’t that much better. We’re lost in a sea of TArgs and TResults for the method signature, and also have one of the dreaded out parameters for our TryGetValue from the cache. Otherwise it’s fairly bland – see if the value is in the cache; if it is, return it, otherwise call the supplied “real” code, and cache that result before passing it back out. Pretty basic chain of responsibility.
Memoize in F#
Here’s nearly the same code but in good old F#!
So this code boils down to pretty much the same as the C# sample, except that all the fluff is gone. From the caller’s point of view, we declare our add function, and then simply call memoize and pass it in. No need for generic arguments, as the F# compiler is smart enough to infer them. We also create a Tuple in F# with syntax that appears to be more like C# method arguments i.e. (5,10). This is succinct, lightweight and easily readable.
For the implementation of the cache, it’s also much cleaner. Firstly, there are no generic type arguments. In fact, there are no explicit types at all except for the Dictionary. F# also handles “out” parameters much more elegantly than C#, so TryGetValue can be easily called and consumed as a single expression.
This was just a fairly short and simple code sample illustrating how type annotations can sometimes quickly get out of control. Having automatic generalisation of functions lets us concentrate on the core functionality of what we’re trying to achieve – the F# version is around 50% of the size of the C# one, but does the same thing. There’s also an example of how nicely F# interoperates with .NET’s out parameters by returning them as part of a Tuple.