I was thinking about this for quite some time. Is function memoization really on

Question

I was thinking about this for quite some time. Is function memoization really only for primitives?

I currently have this piece of code:

Public Shared Function Mize(Of TArg1 As Structure, TResult)(ByVal input_f As System.Func(Of TArg1, TResult)) As System.Func(Of TArg1, TResult)
    Dim map = New System.Collections.Generic.Dictionary(Of TArg1, TResult)
    Return Function(arg1 As TArg1)
               If map.ContainsKey(arg1) Then Return map.Item(arg1)
               Dim result = input_f(arg1)
               map.Add(arg1, result)
               Return result
           End Function
End Function
And I'm wondering should i upgrade TArg1 such that it could accept any arbitrary class?

Explanation / Answer

Is function memoization really only for primitives?

Nope. Who told you that?

I'm wondering should i upgrade TArg1 such that it could accept any arbitrary class?

Absolutely, yes. There's no reason whatsoever that your higher-order method needs to be restricted to functions that take value types, so long as the value you use as the argument is not going to be mutated such that it becomes lost in a hash table. You're not supposed to put objects in a hash table and then mutate them.

I use your technique all the time. Usually something like this in C#:

static Func<A, R> Memoize(this Func<A, R> f)
{
var dict = new Dictionary<A, R>();
return (A arg)=>
{
R result;
if (!dict.TryGetValue(arg, out result))
{
result = f(arg);
dict.Add(arg, result);
}
return result;
};
}
And now you can say:

Func<int, int> fib = null;
fib = x=> x < 2 ? 1 : fib(x-1) + fib(x-2);
fib = fib.Memoize();
And hey presto, you've got a memoized implementation of fib.

Now here's a challenge: do the same for functions of two arguments.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.