Use Memoized Method for Recursive Function

Question

I have a memoizer function like so:

static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var cache = new ConcurrentDictionary<A, R>();
    return argument => cache.GetOrAdd(argument, f);
}

And I also have some recursive method

long TheRecursiveMeth (string inString) {
// recursive function that calls itself    
}

Now, in my main function, I try:

TheRecursiveMeth = TheRecursiveMeth.Memoize();

but the compiler complains

The '.' operator cannot be applied to operand of type `method group'

and

The left-hand side of an assignment must be a variable, a property or an indexer

How do I make calls to TheRecursiveMeth actually call TheRecursiveMeth.Memoize(), including the recursive calls?

Edit: I'm trying to avoid editing the definition of TheRecursiveMeth. Obviously I could just have that check a dictionary.

Edit 2: Since you're interested, I have a function that counts the number of certain palindromes of a given string. It's a little complicated to explain here, but basically something like:

long palCount(string inString) {
    if (inString.Length==1) return 1;
    else {
      count = 0;
      foreach(substring of inString) {
          // more complex logic here 
          count += palCount(subString);
      }
      return count;
    }
}

So clearly this type of thing would benefit from memoization. I avoided adding the algorithm at first because it is irrelevant and is more likely to get people giving me suggestions on that, which is beside the point.

Answer 1

For a fully generalizable solution, you'll have to change the way you write your functions in order to make this all work.

Ignoring the issues you had trying to instantiate your memoized functions, the main problem is that due to early binding, you cannot call your memoized function, the compiler will always bind to the original function. You need to give your function implementation a reference to the memoized version and let it use that. You could achieve that using a factory that takes both a function with the same signature as the memoized function, and the args.

public static Func<TArgs, TResult> Memoized<TArgs, TResult>(Func<Func<TArgs, TResult>, TArgs, TResult> factory, IEqualityComparer<TArgs> comparer = null)
{
    var cache = new ConcurrentDictionary<TArgs, TResult>(comparer ?? EqualityComparer<TArgs>.Default);
    TResult FunctionImpl(TArgs args) => cache.GetOrAdd(args, _ => factory(FunctionImpl, args));
    return FunctionImpl;
}

This then changes functions like:

public long Fib(long n)
{
    if (n < 2L)
        return 1L;
    return Fib(n - 1) + Fib(n - 2);
}

to this:

private Func<long, long> _FibImpl = Memoized<long, long>((fib, n) =>
{
    if (n < 2L)
        return 1L;
    return fib(n - 1) + fib(n - 2); // using `fib`, the parameter passed in
});
public long Fib(long n) => _FibImpl(n);

---

For kicks, here's an implementation of a memoizer interceptor that could be used with the Castle DynamicProxy.

class MemoizedAttribute : Attribute { }

class Memoizer<TArg, TResult> : IInterceptor
{
    private readonly ConcurrentDictionary<TArg, TResult> cache;
    public Memoizer(IEqualityComparer<TArg> comparer = null)
    {
        cache = new ConcurrentDictionary<TArg, TResult>(comparer ?? EqualityComparer<TArg>.Default);
    }
    public void Intercept(IInvocation invocation)
    {
        if (!IsApplicable(invocation))
        {
            invocation.Proceed();
        }
        else
        {
            invocation.ReturnValue = cache.GetOrAdd((TArg)invocation.GetArgumentValue(0),
                _ =>
                {
                    invocation.Proceed();
                    return (TResult)invocation.ReturnValue;
                }
            );
        }
    }
    private bool IsApplicable(IInvocation invocation)
    {
        var method = invocation.Method;
        var isMemoized = method.GetCustomAttribute<MemoizedAttribute>() != null;
        var parameters = method.GetParameters();
        var hasCompatibleArgType = parameters.Length == 1 && typeof(TArg).IsAssignableFrom(parameters[0].ParameterType);
        var hasCompatibleReturnType = method.ReturnType.IsAssignableFrom(typeof(TResult));
        return isMemoized && hasCompatibleArgType && hasCompatibleReturnType;
    }
}

Then just make sure your method is declared virtual and has the appropriate attribute.

public class FibCalculator
{
    [Memoized]
    public virtual long Fib(long n)
    {
        if (n < 2L)
            return 1L;
        return Fib(n - 1) + Fib(n - 2);
    }
}

var calculator = new Castle.DynamicProxy.ProxyGenerator().CreateClassProxy<FibCalculator>(new Memoizer<long, long>());
calculator.Fib(5); // 5 invocations
calculator.Fib(7); // 2 invocations