View the whole series:
In this entry in my C# functional programming series we are finishing up the topic of memoization. If you have not read part 6 then you need to go there and read it now. This entry is going to pick up in the middle of the topic.
In the last part of this series we left off with this method:
public static Func<int,int,int> CachedMultiply()
{
var cache = new Dictionary<Tuple<int,int>, int>();
return (int arg1, int arg2) =>
{
int result;
var arguments = new Tuple<int, int>()
{ One = arg1, Two = arg2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = Multiply(arg1, arg2);
cache.Add(arguments, result);
return result;
}
};
}
We had finally gotten to the point where we had the ability to cache our multiply method with two variables, the only thing left to do is to make this generic. In order to do this, we are going to use generics! Instead of returning Func<int,int,int> from this method we are going to change it to be Func<TArg1,TArg2,TResult>, and then the method now gets a parameter so that we can pass the method to it that we are going to memoize. Here is the generic memoize function that has been converted from the method above.
public static Func<TArg1, TArg2, TResult>
Memoize<TArg1, TArg2, TResult>
(Func<TArg1, TArg2, TResult> func)
{
var cache = new Dictionary<Tuple<TArg1, TArg2>, TResult>();
return (TArg1 argument1, TArg2 argument2) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2>
{ One = argument1, Two = argument2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2);
cache.Add(arguments, result);
return result;
}
};
}
Looks pretty similar, huh? All we really had to do is change all of our types to generic type arguments. So, how would we use this in order to memoize multiply?
var cachedMultiply = Memoize<int,int,int>(Multiply);
int result1 = cachedMultiply(2, 3);
int result2 = cachedMultiply(3, 4);
int result3 = cachedMultiply(2, 3);
It’s a shame that we still have to pass the types to this method, but it is because of method overloading. Since you aren’t passing any type information when you pass Multiply, you are passing a method group, the Memoize function needs to know which method to use. If you are interested in this, you can read more about at Eric Lippert’s Blog. As you can see in the example though, we can now use this Memoize method for any method with two parameters. In order to do a three parameter memoize method, we just add another argument and use a 3-tuple. It would look like this:
public static Func<TArg1, TArg2, TArg3, TResult>
Memoize<TArg1, TArg2, TArg3, TResult>
(Func<TArg1, TArg2, TArg3, TResult> func)
{
var cache = new
Dictionary<Tuple<TArg1, TArg2, TArg3>, TResult>();
return (TArg1 argument1, TArg2 argument2, TArg3 argument3) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2,TArg3>
{ One = argument1, Two = argument2, Three = argument3 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2, argument3);
cache.Add(arguments, result);
return result;
}
};
}
It is identical to the two parameter version except for the addition of an extra type parameter. And this is what we want! We can now repeat this for as many parameters as we want. Since there is no way to really pass a Func with an arbitrary number of parameters, we are stuck with implementing one for every number of arguments. Now you may think that you can get around this with a parameter array, but not really. For example, lets say our method looked like this:
public static int Multiply(params int[] values)
{
if (values.Length == 0)
{
return 0;
}
int result = 1;
foreach (int i in values)
{
result *= i;
}
return result;
}
Which you would call like this:
int result = Multiply(2, 3, 5, 4);
This is just syntactic sugar though. The compiler just turns these variables into an array. So if we wanted to memoize this method call you would want do this:
var cachedMultiply = Memoize<int[], int>(Multiply);
int result = cachedMultiply(3, 4, 5, 6);
The only problem is that this doesn’t work. The method is now seen as a method with a single array parameter, and we would have to call it like this:
var cachedMultiply = Memoize<int[], int>(Multiply);
int result = cachedMultiply(new int[] {3, 4, 5, 6});
Which isn’t terrible, but not ideal either. The other downside to this is that all of the parameters have to have the same types.
Another thing that is also possible with the Memoize function is to make it an extension method. An extension method of what you say? Well, Func<TArg1,TArg2,TResult> of course! You will just change the func parameter to add "this" and there you go. It would end up looking like this:
public static Func<TArg1, TArg2, TResult>
Memoize<TArg1, TArg2, TResult>
(this Func<TArg1, TArg2, TResult> func)
{
var cache = new Dictionary<Tuple<TArg1, TArg2>, TResult>();
return (TArg1 argument1, TArg2 argument2) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2>
{ One = argument1, Two = argument2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2);
cache.Add(arguments, result);
return result;
}
};
}
Calling it is a bit different from what we were doing before. The ideal method would be to just say "Multiply.Memoize()" but we can’t because at this point because "Multiply" is not a delegate and even if it was we don’t have the type info we need. So, in order to call it we have to cast Multiply:
var cachedMultiply = ((Func<int,int,int>)Multiply).Memoize();
var result1 = cachedMultiply(2, 3);
This may look clumsy when you are calling it like this, but if you have a method where a delegate is being passed in this will work very nice:
public void RunThis(Func<int, int, int> method)
{
var cachedMethod = method.Memoize();
cachedMethod(2, 3);
}
Wow, is this over yet? Thankfully yes. We have now completed my tutorial on memoization. We have seen how to make our Memoize method generic so that we can call it using any method, all we have to do is implement the memoize methods for each number of parameters into a library along with the tuples, and voila, we can use them wherever we need to. I hope you enjoyed this post, and I will be back soon with my next functional programming entry. I’m sure there are parts of this that are not clear, so please leave me a comment if you don’t understand something!
If you liked it, please vote for it below!
Loved the article? Hated it? Didn’t even read it?
We’d love to hear from you.
