Currying und partielle Funktionsapplikation

Vor einiger Zeit habe ich mich (hier) mit Currying und partieller Funktionsapplikation in C# 3.0 beschäftigt. Ich will in diesem Eintrag die Implementation von Wes aufgreifen und anschauen wie eine solche in Scheme und Ruby aussehen könnte.

Grundlage ist die simple Addition:

Func<int,int,int> add = (x,y) => x + y;

Die Funktion Curry für eine generische Funktion mit zwei Argumenten kann in C# als Extension Method implementiert werden und sieht in der Implementation von Wes Dyer folgendermassen aus:

public static Func<A, Func<B, R>> Curry<A, B, R>(
                  this Func<A, B, R> f)
{
return a => b => f(a, b);
}

Mit dieser Funktion ist es also möglich, die Argumente schrittweise zu binden wie wir in der Anwendung klar erkennen können:

Func<int,Func<int,int>> curriedAdd = add.Curry();
Console.WriteLine(curriedAdd(3)(5)); //8

Wie Wes weiter erklärt, kann dieses Konzept weiter generalisiert werden in ein Konzept mit dem Namen 'partielle Funktionsapplikation'. Mit diesem Konzept ist es möglich aus einer Funktion eine ganze Familie von Funktionen zu erzeugen. In unserem Beispiel wollen wir bei der Funktion add das erste Argument mit 1 binden und so eine triviale Inkrementierungs-Funktion erhalten.

Func<int, int> inc = add.Partial(1);

Die Funktion Partial zitiere ich auch wieder direkt von Wes. Sie sieht folgendermassen aus:

public static Func<B, R> Partial<A, B, R>(
                   this Func<A, B, R> f, A a)
{
return b => f(a, b);
}

Thanks again, Wes!

Wenn ich mir das so anschaue, erinnert es mich ein klein wenig an das Überladen von Methoden in der Objektorientierung. Mit beiden Konzepten ist es möglich, den Aufruf einer Funktion/Methode zu vereinfachen indem bestimmte alternative Signaturen angeboten werden. (Die Puristen unter euch mögen mir diesen profanen Vergleich verzeihen!)

Als relativer Anfänger im Umgang mit Scheme habe ich mir angeschaut wie eine solche Implementation in diesem LISP-Dialekt aussehen könnte. Für die Curry-Funktion bin ich auf folgende Implementation gekommen.

(define add
 (lambda (a b)
   (+ a b)))

(define curry
 (lambda (f)
   (lambda (a)
     (lambda (b)
       (f a b)))))

(define curried-add (curry add))
((curried-add 3) 5)  ;; => 8

Auffallend ist hier, dass ich kein funktionales Äquivalent für 'Extension Methods' gefunden habe. Erfahrenere Scheme Benutzer könnten hier vermutlich mit einer prägnanteren Implementation aufwarten.

Trotzdem hier auch noch die Implementation von Partial:

(define partial
 (lambda (f a)
   (lambda (b)
     (f a b))))

(define inc (partial add 1))
(inc 3) ;; => 4

Jetzt wollen wir aber auch noch sehen wie das ganze in Ruby aussehen könnte. Zuerst die Funktion Curry:

add = lambda{|a,b| a + b}
class << add
  def curry
    lambda{|a| lambda{|b| self.call(a,b)}}
  end
end

curried_add = add.curry
curried_add.call(3).call(6)   # => 9

Hier habe ich es vorgezogen, Curry auf dem Objekt add zu implementieren da mir die Anwendung so einfacher schien. Und schliesslich auch eine Ruby-Version von Partial:

class << add
  def partial val
    lambda{|a| self.call(a,val)}
  end
end

inc = add.partial 1
inc 4   # => 5

Wenn ich die verschiedenen Implementation miteinander vergleiche, fällt mir persönlich zuerst einmal der etwas grössere Programmieraufwand für C# auf. Es wird wieder einmal die Tatsache deutlich, dass es sich um eine statisch typisierte Sprache handelt und wir zugunsten einer Typenprüfung beim Kompilieren etwas mehr schreiben müssen. Bei der Ruby-Version fällt vor allem der explizite Aufruf von Proc#call auf.

Als nächstes gäbe es dann wohl den Y-Combinator in der verschiedenen Sprachen zu vergleichen.