Benutzer:Diaspomod/currying

Currying (vor allem in der Linguistik auch Schönfinkeln) ist die Umwandlung einer Funktion mit mehreren Argumenten in eine Sequenz von Funktionen mit jeweils einem Argument. Obwohl das Verfahren von Moses Schönfinkel^[1] erfunden und von Gottlob Frege^[2] vorausgedacht wurde, wird es oft nach Haskell Brooks Curry benannt, der das Verfahren letztlich umfangreich theoretisch ausgearbeitet hat.^[3]

Verfahren

Es sei eine Funktion gegeben, die n Argumente erfordert. Wird diese auf ein Argument angewendet, so konsumiert sie nur genau dieses und liefert als Funktionswert eine weitere Funktion, die noch $n-1$ Argumente verlangt. Die zurückgegebene Funktion wird anschließend auf alle weiteren Argumente angewendet.

In Typen ausgedrückt, handelt es sich um die Umrechnung einer Funktion $f\colon A_{1}\times \ldots \times A_{n}\to B$ zu einer modifizierten Funktion $f_{curried}\colon A_{1}\to (A_{2}\to (\ldots (A_{n}\to B)\ldots ))$ .^[4]

Eine alternative Schreibweise ist $\operatorname {curry} (f)=f_{curried}$ , wobei $\operatorname {curry}$ als ein Operator verstanden wird, der $n$ -stellige Abbildungen (für $n>1$ ) modifiziert zu einer einstelligen Abbildung, deren Bildwerte einstellige Abbildungen sind usw., wobei der Reihe nach alle Argumente der ursprünglichen Abbildung durchlaufen werden; formal:

\operatorname {curry} \colon (A_{1}\times \ldots \times A_{n}\to B)\,\to \,(A_{1}\to (A_{2}\to (\ldots (A_{n}\to B)\ldots )))

.

Das Konzept des Currying ist verwandt, aber (für $n>2$ ) verschieden, von dem der partiellen Anwendung wie etwa:

f(a_{1},a_{2},\ldots a_{n-1},\cdot )\colon A_{n}\to B,a_{n}\mapsto f(a_{1},a_{2},\ldots a_{n})

,

f(a_{1},\underbrace {\cdot ,\ldots ,\cdot } _{(n-1){\text{-mal}}}))\colon A_{2}\times \ldots \times A_{n}\to B,(a_{2},\dots ,a_{n})\mapsto f(a_{1},a_{2},\ldots a_{n})

.

Im einstelligen Fall ( $n=1$ ) hat Currying keine Auswirkung:

f_{curried}=f

,

im zweistelligen Fall ( $n=2$ ) besteht der Zusammenhang

f_{curried}\colon A_{1}\to (A_{2}\to B),a_{1}\mapsto f(a_{1},\cdot )

, d. h. für alle

a_{1}\in A_{1}

:

f_{curried}(a_{1})=f(a_{1},\cdot )

,

im dreistelligen Fall ( $n=3$ ) gilt für $a_{1}\in A_{1}$ :

f_{curried}(a_{1})\colon A_{2}\to (A_{3}\to B),a_{2}\mapsto f(a_{1},a_{2},\cdot )

, und mit zusätzlich

a_{2}\in A_{2}

:

f_{curried}(a_{1})(a_{2})\colon A_{3}\to B,a_{3}\mapsto f(a_{1},a_{2},\cdot )

, d. h.

f_{curried}(a_{1})(a_{2})=f(a_{1},a_{2},\cdot )

,

allgemein:

f_{curried}(a_{1})(a_{2})\dots (a_{n})=f(a_{1},a_{2},\dots ,a_{n})

,

f_{curried}(a_{1})(a_{2})\dots (a_{n-1})=f(a_{1},a_{2},\dots ,a_{n-1},\cdot )

.^[5]

Im Allgemeinen kommt es häufig vor, dass eine mehrstellige Abbildung nicht für alle Wertekombinationen aus den Trägermengen $A_{1},\dots ,A_{n}$ definiert ist, also nur auf einer Teilmenge des kartesischen Produkts $R=D_{f}\subseteq A_{1}\times \cdots \times A_{n}$ , d. h. auf (dem Graph einer) Relation.^[6] Man kann diese Situation behandeln, in dem man entweder grundsätzlich partielle Abbildungen zulässt und die obigen Definitionen formal übernimmt. Hält man dagegen am Konzept totaler Abbildungen fest, werden die Definitionsbereiche der beteiligten Abbildungen von der Wahl bereits festgelegter Parameter abhängig, wie das Beispiel zweistelliger Abbildungen zeigt:

f_{curried}(a_{1})=f(a_{1},\cdot )

;

der Definitionsbereich dieser Abbildung ist von $a_{1}$ abhängig:

\{a_{2}\in A_{2}|\exists a_{1}\in A_{1}:(a_{1},a_{2})\in D_{f}\}=R^{\leftarrow }(\{a\})

,

also die Urbildfaser von $a_{1}$ bezüglich des als Relation aufgefassten Definitionsbereichs $R=D_{f}$ .^[7]

Da für n=1 gilt $f_{curried}=f$ , kann für $f_{curried}$ dasselbe Symbol verwendet werden wie für $f$ . Man nennt dies Überladung (siehe auch Signatur (Modelltheorie) §Anmerkungen).^[8]

Beispiele

Lambda-Notation

Ein Beispiel in Lambda-Notation soll das Verfahren verdeutlichen, wobei die Funktion konkret folgendermaßen definiert sei:

$\lambda x\ y\ z\ .\ x\ y\ z$

Die Funktion verlangt also 3 Argumente und gibt diese zurück. Die Definition ist äquivalent zu:

$\lambda x.\lambda y.\lambda z\ .\ x\ y\ z$

Bei der Anwendung der Funktion auf die Argumente a, b und c geschieht Folgendes:

$\left(\lambda x.\lambda y.\lambda z\ .\ x\ y\ z\right)\ a\ b\ c\ {\mathsf {-\ Die\ Anwendung}}$

$\left(\lambda y.\lambda z\ .\ a\ y\ z\right)\ b\ c$

$\left(\lambda z\ .\ a\ b\ z\right)\ c$

$a\ b\ c\ {\mathsf {-\ Resultat}}$

Nach erstmaliger Anwendung der Funktion auf a, b und c wird x im Funktionskörper durch das erste Argument a ersetzt. Das Resultat ist eine Funktion, die noch die Argumente y und z verlangt. Diese wird sofort auf b und c angewendet.

Überladung

Angenommen, wir haben eine zweistellige Multiplikationsfunktion $\operatorname {mult}$ , die zwei ganze Zahlen multipliziert, d. h. einem Paar ganzer Zahlen ihr Produkt zuordnet:

\operatorname {mult} \colon \,{\begin{cases}\mathbb {N} \times \mathbb {N} \to \mathbb {N} \\(m,n)\mapsto m*n\end{cases}}

mit

\operatorname {mult} (m,n)=m*n

^[9]

Per Definition wird diese Funktion auf zwei natürliche Zahlen angewendet und eine natürliche Zahl zurückgegeben, beispielsweise $\operatorname {mult} (2,3)=6$ .

Wird nun zunächst das erste Argument besetzt (etwa mit $2$ ), das zweite noch freigelassen, entsteht eine einstellige ‚höhere Funktion’, die selbst ein (weiteres) Argument aufnimmt und das Produkt mit diesem festen Parameter (der Nummer $2$ ) zurückgibt:

\operatorname {mult} (2,\cdot )\colon \,

{\begin{cases}\mathbb {N} \to \mathbb {N} \\n\mapsto 2*n\end{cases}}

und für ein beliebiges festes erstes Argument $m\in \mathbb {N}$ :

\operatorname {mult} (m,\cdot )\colon \,

{\begin{cases}\mathbb {N} \to \mathbb {N} \\n\mapsto m*n\end{cases}}\,

.

Currying bedeutet nun bei einer n-stelligen Funktion, diesen Vorgang solange durchzuführen, bis nur eine noch einstellige höhere Funktion übrigbleibt. Für n=2 ist daher:

\operatorname {mult} _{curried}\colon \,{\begin{cases}\mathbb {N} \to (\mathbb {N} \to \mathbb {N} )\\m\mapsto \operatorname {mult} (m,\cdot )\end{cases}}\,

^[10]

Da die Bezeichnung $\operatorname {mult}$ als einstellige Funktion noch unbesetzt ist, kann diese überladen werden,^[11] d. h. im einstelligen Fall wird $\operatorname {mult}$ als $\operatorname {mult} _{curried}$ verstanden:

\operatorname {mult} (m)(n)=\operatorname {mult} _{curried}(m)(n)=\operatorname {mult} (m,n)=m*n

.

Geometrisches Beispiel

f(x, y) = x^2 + x y + y^2

Man kann sich die Situation für eine Funktion mit zwei Argumenten $z=f(x,y)$ wie folgt vorstellen: das Fixieren einer Argumentvariable entspricht einer Einschränkung der zweidimensionalen Definitionsmenge auf eine eindimensionale Teilmenge, z. B. $y=1$ , die resultierende Funktion entspricht der Schnittkurve des Graphen von $f(x,y)$ mit der Ebene aller Punkte $(x,1,z)$ . Alle Punkte $(x,y,z)$ des Graphen können somit auch durch eine zweistufige Auswahl erreicht werden: zunächst durch die Festlegung der Schnittebene $y=1$ und dann durch die Auswertung der Schnittkurve $s(x)=f(x,y)|_{y=1}$ an der Stelle $x$ .

Anwendung

Currying wird überwiegend in Programmiersprachen und Kalkülen verwendet, in denen Funktionen nur ein einzelnes Argument erhalten dürfen. Dazu gehören beispielsweise ML, Unlambda und der Lambda-Kalkül sowie das nach Curry benannte Haskell. Viele dieser Sprachen bieten dem Programmierer allerdings syntaktische Möglichkeiten, dies zu verschleiern. Ein Beispiel hierfür ist die Äquivalenz der Funktionsdefinition im oben gezeigten Beispiel.

JavaScript

Das nachfolgende Beispiel zeigt Currying in JavaScript. Zunächst wird eine Funktion uncurriedAdd definiert, die als Ergebnis die Summe der beiden Argumente hat. Andererseits wird eine Funktion curriedAdd definiert, die eine als Closure definierte Funktion zurückgibt, welche partiell angewendet werden kann.

function uncurriedAdd(x, y) {
    return x + y;
}

function curriedAdd(x) {
    return function(y) {
        return x + y;
    };
}

console.log(uncurriedAdd(3, 5)); // 8
console.log(curriedAdd(3)(5)); // 8

const addThree = curriedAdd(3);
console.log(addThree(5)); // 8
console.log(addThree(12)); // 15

Durch Currying wird die Funktion partiell angewendet, wobei die Funktionsargumente nacheinander übergeben werden und zwischenzeitlich in einer neuen Funktion gehalten werden, die beliebig weiterverwendet werden kann.

Die Funktionen können in JavaScript mit anonymen Funktionen auch kürzer definiert werden:

const uncurriedAdd = (x, y) => x + y;
const curriedAdd = x => y => x + y;

Java

import java.util.function.*; 

class Main {
    static IntBinaryOperator uncurriedAdd = (x, y) -> x + y;
    static IntFunction<IntUnaryOperator> curriedAdd = x -> y -> x + y;

    public static void main(String[] args) {
        System.out.println(uncurriedAdd.applyAsInt(3, 5)); // 8
        System.out.println(curriedAdd.apply(3).applyAsInt(5)); // 8

        var addThree = curriedAdd.apply(3);
        System.out.println(addThree.applyAsInt(5)); // 8
        System.out.println(addThree.applyAsInt(12)); // 15
    }
}

Kotlin

val uncurriedAdd = { x: Int, y: Int -> x + y }
val curriedAdd = { x: Int -> { y: Int -> x + y } }

println(uncurriedAdd(3, 5)) // 8
println(curriedAdd(3)(5)) // 8

val addThree = curriedAdd(3)
println(addThree(5)) // 8
println(addThree(12)) // 15

C++

C++ führte den Lambda-Kalkül mit anonymen Funktionen in die Sprache ein. Mit dem Schlüsselwort auto wird durch Typinferenz der Datentyp implizit abgeleitet, ohne den Datentypen explizit deklarieren zu müssen. Dadurch ergibt sich eine kürzere Schreibweise für die Currifizierung:

#include <iostream>

int uncurriedAdd(int x, int y) {
    return x + y;
}

auto curriedAdd(int x) {
    return [x](int y) {
        return x + y;
    };
}

int main() {
    using namespace std;
    cout << uncurriedAdd(3, 5) << endl; // 8
    cout << curriedAdd(3)(5) << endl; // 8

    auto addThree = curriedAdd(3);
    cout << addThree(5) << endl; // 8
    cout << addThree(12) << endl; // 15
}

Man beachte, dass die Erwähnung des Typs int im Argument des Lambda-Ausdrucks auch durch auto ersetzt werden kann, wodurch die Implementierung verallgemeinert wird. Die Parameter der benannten Funktion curried_add kann jedoch nur durch Templates für verschiedene Datentypen verallgemeinert werden.

C

Da es in der Programmiersprache C keine anonymen Funktionen gibt, wird eine benannte Funktion add separat definiert, die von curriedAdd zurückgegeben wird. Der Wert von x wird in der globalen Variablen z gespeichert, da die Funktion add nicht auf die Continuation der Funktion curriedAdd zugreifen kann.

#include <stdio.h>

int uncurriedAdd(int x, int y) {
    return x + y;
}

int z;

int add(int y) {
    return y + z;
}

typedef int function(int);

function* curriedAdd(int x) {
    z = x;
    return add;
}

int main() {
    printf("%d\n", uncurriedAdd(3, 5)); // 8
    printf("%d\n", curriedAdd(3)(5)); // 8

    function* addThree = curriedAdd(3);
    printf("%d\n", addThree(5)); // 8
    printf("%d\n", addThree(12)); // 15
}

C#

using System;

class Program {
    static Func<int, int, int> uncurriedAdd = (x, y) => x + y;
    static Func<int, Func<int, int>> curriedAdd = x => y => x + y;

    public static void Main() {
        Console.WriteLine(uncurriedAdd(3, 5)); // 8
        Console.WriteLine(curriedAdd(3)(5)); // 8

        var addThree = curriedAdd(3);
        Console.WriteLine(addThree(5)); // 8
        Console.WriteLine(addThree(12)); // 15
    }
}

F#

let uncurriedAdd (x, y) = x + y
let curriedAdd x y = x + y

printfn "%i" (uncurriedAdd (3, 5)) // 8
printfn "%i" ((curriedAdd 3) 5) // 8
printfn "%i" (curriedAdd 3 5) // 8

let addThree = curriedAdd 3
printfn "%i" (addThree 5) // 8
printfn "%i" (addThree 12) // 15

Haskell

In der Programmiersprache Haskell kann eine Funktion genau einen oder keinen Parameter haben. Wenn man eine Funktion mit mehreren Argumenten aufrufen möchte, müssen die Argumente zuerst in einem neuen Objekt zusammengesetzt werden, sodass die Funktion nur ein Argument erhält. Dafür können die Parameter in runden Klammern mit Kommata getrennt aufgelistet werden, um ein Tupel zu definieren.

uncurriedAdd (x, y) = x + y

Eine Alternative dazu ist das Currying. In der expliziten Schreibweise definiert man für jeden Wert im Tupel jeweils eine Funktion mit nur einem Argument. Solange noch nicht alle Argumente übergeben wurden, wird eine Funktion zurückgegeben, die ein Teilergebnis liefert.

curriedAdd x = \y -> x + y

Da die Schreibweise mit mehreren Lambda-Funktionen umständlich sein kann, gibt es eine syntaktisch gezuckerte Notation, die semantisch äquivalent ist. Schreibt man die Argumente ohne runde Klammern hintereinander, erhält man automatisch eine currifizierte Funktion.

curriedAdd x y = x + y

Die currifizierte Funktion kann sowohl explizit, als auch implizit partiell angewendet werden.

main = do
    print (uncurriedAdd (3, 5)) -- 8
    print ((curriedAdd 3) 5) -- 8
    print (curriedAdd 3 5) -- 8

    let addThree = curriedAdd 3
    print (addThree 5) -- 8
    print (addThree 12) -- 15

Zudem gibt es in Haskell die Möglichkeit eine Funktion im Nachhinein zwischen currifizierter und nicht currifizierter Definition umzuwandeln. Dafür werden die Funktionen curry und uncurry verwendet.

main = do
    let uncurried = uncurry curriedAdd
    print (uncurried (3, 5)) -- 8
    
    let curried = curry uncurriedAdd
    print ((curried 3) 5) -- 8
    print (curried 3 5) -- 8

    let addThree = curried 3
    print (addThree 5) -- 8
    print (addThree 12) -- 15

Python

def uncurriedAdd(x, y):
    return x + y

def curriedAdd(x):
    return lambda y: x + y

print(uncurriedAdd(3, 5)) # 8
print(curriedAdd(3)(5)) # 8

addThree = curriedAdd(3)
print(addThree(5)) # 8
print(addThree(12)) # 15

Ruby

def uncurriedAdd(x, y)
    return x + y
end

def curriedAdd(x)
    return lambda { |y| x + y }
end

puts uncurriedAdd(3, 5) # 8
puts curriedAdd(3).call(5) # 8

addThree = curriedAdd(3)
puts addThree.call(5) # 8
puts addThree.call(12) # 15

Es gibt in der Programmiersprache Ruby zusätzlich die Möglichkeit, ein Funktionsobjekt erst beim Funktionsaufruf zu currifizieren.

uncurriedAdd = lambda { |x, y| x + y }
puts uncurriedAdd.call(3, 5) # 8
puts uncurriedAdd.curry[3][5] # 8

addThree = uncurriedAdd.curry[3]
puts addThree.call(5) # 8
puts addThree.call(12) # 15

Scheme

(define uncurriedAdd (lambda (x y)
    (+ x y)))

(define curriedAdd (lambda (x)
    (lambda (y)
        (+ x y))))

(display (uncurriedAdd 3 5)) (newline) ; 8
(display ((curriedAdd 3) 5)) (newline) ; 8

(define addThree (curriedAdd 3))

(display (addThree 5)) (newline) ; 8
(display (addThree 12)) (newline) ; 15

Tcl

proc uncurriedAdd {x y} {
    expr {$x + $y}
}

proc curriedAdd x {
    list apply [list y [format {expr {%d + $y}} $x]]
}

puts stdout [uncurriedAdd 3 5]; # 8
puts stdout [{*}[curriedAdd 3] 5]; # 8

set addThree [curriedAdd 3]
puts stdout [{*}$addThree 5]; # 8
puts stdout [{*}$addThree 12]; # 15

Einzelnachweise und Anmerkungen

↑ Moses Schönfinkel: Über die Bausteine der mathematischen Logik. In: Mathematische Annalen 92 (1928). S. 305–316, Digitalisat.
↑ Gottlob Frege: Grundgesetze der Arithmetik. Hermann Pohle, Jena 1893 (Band I) 1903 (Band II) korpora.org.
↑ Haskell Brooks Curry, Robert Feys, Roger Hindley, Jonathan P. Seldin: Combinatory Logic. North Holland, 2 Bände, 1958, 1972.
↑ Dabei bezeichnet $(X\to Y)$ oder $[X\to Y]$ die Menge der Abbildungen von $X$ nach $Y$ .
↑ Im nullstelligen Fall (n=0) würde das Currying einer Abbildung $f$ ohne Parameter und mit einem Wert $b\in B$ eine einstellige Abbildung mit konstantem Wert $b$ zuordnen, also etwa
$f_{curried}:B\to B,x\mapsto b$ .
↑ Ein Beispiel ist $f(a_{1},a_{2}):=a_{1}/(a_{1}-a_{2})$ mit $a_{1},a_{2}\in \mathbb {R} \setminus \Delta _{\mathbb {R} }$ (wobei $\Delta _{\mathbb {R} }$ die Diagonale $\{(a_{1},a_{2})\in \mathbb {R} ^{2}|a_{1}=a_{2}\}$ bezeichnet).
↑ Im obigen Beispiel ist dies $\mathbb {R} \setminus \{a_{1}\}$ .
↑ Voraussetzung ist, dass das Symbol $f$ nicht schon anderweitig mit Stelligkeit 1 überladen ist (siehe Beispiel unten, dies zwingt zwischen $\operatorname {mult}$ und $\operatorname {prod}$ zu unterscheiden).
↑ Zur Unterscheidung vom Platzhalter $\cdot$ wird hier $*$ als Multiplikationszeichen verwendet.
↑ Dieser Funktion könnte man auch einen eigenen Namen vergeben:
$\operatorname {doppelt} :=\operatorname {mult} _{curried}(2)=\operatorname {mult} (2,\cdot ):\mathbb {N} \to \mathbb {N}$
mit $\operatorname {doppelt} (n)=2*n$ .
↑ Man unterscheide zwischen $\operatorname {mult}$ und der überladenen Funktion $\operatorname {prod}$ mit $\operatorname {prod} (k_{1},\cdots ,k_{r})=\prod _{i=1}^{r}k_{i}$ zur Stelligkeit $r$ und Faktoren $k_{i}\in \mathbb {N}$ . Zwar ist zweistellig $\operatorname {mult} (m,n)=\operatorname {prod} (m,n)=m*n$ , aber einstellig ist $\operatorname {prod} (m)=m$ , während $\operatorname {mult} (m)=\operatorname {mult} _{curried}(m)=\operatorname {mult} (m,\cdot )$ eine einstellige Funktion ist.

Kategorie:Programmierung Kategorie:Theoretische Informatik

[1] Moses Schönfinkel: Über die Bausteine der mathematischen Logik. In: Mathematische Annalen 92 (1928). S. 305–316, Digitalisat.

[2] Gottlob Frege: Grundgesetze der Arithmetik. Hermann Pohle, Jena 1893 (Band I) 1903 (Band II) korpora.org.

[3] Haskell Brooks Curry, Robert Feys, Roger Hindley, Jonathan P. Seldin: Combinatory Logic. North Holland, 2 Bände, 1958, 1972.

[4] Dabei bezeichnet $(X\to Y)$ oder $[X\to Y]$ die Menge der Abbildungen von $X$ nach $Y$ .

[5] Im nullstelligen Fall (n=0) würde das Currying einer Abbildung $f$ ohne Parameter und mit einem Wert $b\in B$ eine einstellige Abbildung mit konstantem Wert $b$ zuordnen, also etwa
$f_{curried}:B\to B,x\mapsto b$ .

[6] Ein Beispiel ist $f(a_{1},a_{2}):=a_{1}/(a_{1}-a_{2})$ mit $a_{1},a_{2}\in \mathbb {R} \setminus \Delta _{\mathbb {R} }$ (wobei $\Delta _{\mathbb {R} }$ die Diagonale $\{(a_{1},a_{2})\in \mathbb {R} ^{2}|a_{1}=a_{2}\}$ bezeichnet).

[7] Im obigen Beispiel ist dies $\mathbb {R} \setminus \{a_{1}\}$ .

[8] Voraussetzung ist, dass das Symbol $f$ nicht schon anderweitig mit Stelligkeit 1 überladen ist (siehe Beispiel unten, dies zwingt zwischen $\operatorname {mult}$ und $\operatorname {prod}$ zu unterscheiden).

[9] Zur Unterscheidung vom Platzhalter $\cdot$ wird hier $*$ als Multiplikationszeichen verwendet.

[10] Dieser Funktion könnte man auch einen eigenen Namen vergeben:
$\operatorname {doppelt} :=\operatorname {mult} _{curried}(2)=\operatorname {mult} (2,\cdot ):\mathbb {N} \to \mathbb {N}$
mit $\operatorname {doppelt} (n)=2*n$ .

[11] Man unterscheide zwischen $\operatorname {mult}$ und der überladenen Funktion $\operatorname {prod}$ mit $\operatorname {prod} (k_{1},\cdots ,k_{r})=\prod _{i=1}^{r}k_{i}$ zur Stelligkeit $r$ und Faktoren $k_{i}\in \mathbb {N}$ . Zwar ist zweistellig $\operatorname {mult} (m,n)=\operatorname {prod} (m,n)=m*n$ , aber einstellig ist $\operatorname {prod} (m)=m$ , während $\operatorname {mult} (m)=\operatorname {mult} _{curried}(m)=\operatorname {mult} (m,\cdot )$ eine einstellige Funktion ist.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]