Linq und Memoization

Gestern habe ich mir ein Video von Wes Dyer angeschaut. In diesem Interview beschreibt Wes (ein Mitarbeiter des C#-Kompiler-Teams und ein ziemlich smarter Typ) die Vereinfachung eines Singleton-Pattern mittels Extension Methods. Da mir das ganz gut gefallen hat, beschloss ich das ganze mit der Beta von 'Orcas' auszuprobieren und hier nachzuvollziehen. Nachfolgend also dieses Beispiel.

Eine typische Implementation des Singleton-Pattern sieht meist etwa so aus:

    public class Foo
    {
        private static Foo _instance = null;

        public static Foo GetInstance()
        {
            if (_instance == null)
                _instance = CreateFoo();

            return _instance;
        }

        private static Foo CreateFoo()
        {
            //some interesting stuff
            return new Foo();
        }
    }

Das ist soweit trivial und sollte keinem von uns Kopfzerbrechen bereiten. (Auf den Sinn und die Notwendigkeit des Patterns und allfällige Singletonitis wollen wir hier nicht eingehen) In einigen Sprachen ist dieses Pattern bereits sogar in die Standart-Bibiliothek integriert worden. (e.g Ruby)

Etwas – zugegebenermassen nur sehr wenig – komplizierter wird es hier, wenn wir Gruppen von Instanzen verwalten wollen. Zum Beispiel stellen wir uns für das gegebene Beispiel vor, dass wir pro Zahl eine eigene Instanz verwalten wollen. Ein erster Versuch könnte uns zum Beispiel zu folgender Implementation führen:

   public class ComplicatedFoo
   {
      private static Dictionary<int,ComplicatedFoo> 
       _dictionary = new Dictionary<int,ComplicatedFoo>();
 
       public static ComplicatedFoo GetInstance(int n)
       {
           ComplicatedFoo foo = null;
           if (!_dictionary.TryGetValue(n, out foo))
           {
               foo = CreateComplicatedFoo(n);
               _dictionary.Add(n, foo);
           }
           return foo;
       }
 
       private static ComplicatedFoo 
                           CreateComplicatedFoo(int n)
       {
           //some interesting stuff
           return new ComplicatedFoo();
       }
   }

Wir nehmen also erstmal ein Dictionary zu Hilfe um diese Struktur abzubilden. Wenn wir dies aber genauer anschauen, stellen wir fest, dass es sich hier um die Verbindung von einer Funktion (inkl. Parameter) und einem Resultat handelt. Mit anderen Worten: Memoization.
Memoization implementieren wir in C# 3.0 mittels einer ‚Extension Method’. Im unserem Fall mit einer Methode mit einem Argument und einem Resultat könnte diese Methode so aus:

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

Wenn wir nun diese Memoization-Funktion auf unsere vorige Implementation anwenden, so führt uns das zu folgendem Code:

    public class FunctionalFoo
    {
        private static Func<int, FunctionalFoo> 
           getInstance = ((Func<int, FunctionalFoo>)
                 (n => CreateFunctionalFoo(n))).Memoize();

        public static FunctionalFoo GetInstance(int n)
        {
            return getInstanceMemoized(n);
        }

        private static FunctionalFoo 
                               CreateFunctionalFoo(int n)
        {
            //some interesting stuff
            return new FunctionalFoo();
        }
    }

Der Vorteil dieser Implementation ist natürlich, dass wir unsere Memoize-Funktion beliebig wiederverwenden können. (Gesetzt wir haben die entsprechende Signatur in unsere CreateFoo-Methode.)

Ziemlich cool IMHO. Thanks Wes!