How do I write a generic memoize function?

Question

I'm writing a function to find triangle numbers and the natural way to write it is recursively:

function triangle (x)
   if x == 0 then return 0 end
   return x+triangle(x-1)
end

But attempting to calculate the first 100,000 triangle numbers fails with a stack overflow after a while. This is an ideal function to memoize, but I want a solution that will memoize any function I pass to it.

Answer 1

See this blog post for a generic Scala solution, up to 4 arguments.

Answer 2

In C# 3.0 - for recursive functions, you can do something like:

public static class Helpers
{
    public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>,  R> f)
    {
        var map = new Dictionary<A, R>();
        Func<A, R> self = null;
        self = (a) =>
        {
            R value;
            if (map.TryGetValue(a, out value))
                return value;
            value = f(a, self);
            map.Add(a, value);
            return value;
        };
        return self;
    }        
}

Then you can create a memoized Fibonacci function like this:

var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));

Answer 3

Recursion isn't necessary. The nth triangle number is n(n-1)/2, so...

public int triangle(final int n){
   return n * (n - 1) / 2;
}

Answer 4

In Perl generic memoization is easy to get. The Memoize module is part of the perl core and is highly reliable, flexible, and easy-to-use.

The example from it's manpage:

# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments);    # Is faster than it was before

You can add, remove, and customize memoization of functions at run time! You can provide callbacks for custom memento computation.

Memoize.pm even has facilities for making the memento cache persistent, so it does not need to be re-filled on each invocation of your program!

Here's the documentation: http://perldoc.perl.org/5.8.8/Memoize.html

Answer 5

Here is a generic C# 3.0 implementation, if it could help :

public static class Memoization
{
    public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
    {
        var cache = new Dictionary<T, TResult>();
        var nullCache = default(TResult);
        var isNullCacheSet = false;
        return  parameter =>
                {
                    TResult value;

                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

                    value = function(parameter);
                    cache.Add(parameter, value);
                    return value;
                };
    }
}

(Quoted from a french blog article)

Answer 6

In Scala (untested):

def memoize[A, B](f: (A)=>B) = {
  var cache = Map[A, B]()

  { x: A =>
    if (cache contains x) cache(x) else {
      val back = f(x)
      cache += (x -> back)

      back
    }
  }
}

Note that this only works for functions of arity 1, but with currying you could make it work. The more subtle problem is that memoize(f) != memoize(f) for any function f. One very sneaky way to fix this would be something like the following:

val correctMem = memoize(memoize _)

I don't think that this will compile, but it does illustrate the idea.