Funktionsdefinition und Signatur

In diesem Kapitel wird die Funktionsdefinition und Signatur von funktionalen Algorithmen behandelt.

Funktionsdefinition

Eine Funktion f ist eine Relation zwischen einer Eingabemenge X und einer Ausgabemenge $Y(f\subseteq X*Y)$ mit der Eigenschaft:

Für alle x ∈ X, y,y‘ ∈ Y mit (x,y),(x,y‘) ∈ f gilt y=y‘

Wir schreiben dann üblicherweise f(x)=y anstatt(x,y)∈ f und deklarieren eine Funktion durch $f:X\to Y$ . Ist $f:X\to Y$ eine Funktion so heißt X Eingabemenge und Y Ausgabemenge. In der funktionalen Programmierung sind Ein‐ und Ausgabemengen üblicherweise Terme eines bestimmten Typs.

Termdefinition

Sei T ein Typ, $V_{T}$ eine Menge von Variablen vom Typ T und $C_{T}$ eine Menge von Konstanten vom Typ T. Dann ist jedes $X\in V_{T}$ ist ein Term vom Typ T, jedes $a\in C_{T}$ ein Term vom Typ T und ist $f:T^{k}\to T$ eine Funktion und $t_{1},...,t_{k}$ sind Terme vom Typ T, so ist $f(t_{1},...,t_{k})$ ein Term vom Typ T.

Beispiel Terme natürlicher Zahlen

Sei int der Typ der natürlichen Zahlen, $V_{int}$ eine Menge von Variablen vom Typ $T_{int}$ und $C_{int}=\mathbb {N} ={1,2,3...}$ . Mögliche Funktionen auf natürliche Zahlen sind

$+:int$ x $int\to int$
$*:int$ x $int\to int$

3+4, (8+9)*10, X*4+1 sind dann Terme natürlicher Zahlen.

Beispiel Bool´sche Terme

Sei bool der Typ der Bool´sche Terme, $V_{bool}$ eine Menge von Variablen vom Typ $T_{bool}$ und $C_{bool}={true,false}$ . Mögliche Funktionen auf Bool´sche Termes sind

$\bigwedge :bool$ x $bool\to bool$
$\neg :bool\to bool$

true $\bigwedge$ und $\neg Y\bigwedge X$ sind dann Bool´sche Terme.

Sind $v_{1},...,v_{n}$ Unbestimmte vom Typ $T_{1},...,T_{n}$ (bool oder int) und ist $t(v_{1},...,v_{n})$ ein Term, so heißt $f(v_{1},...,v_{n}):=t(v_{1},...,v_{n})$ eine Funktionsdefinition vom Typ T.

T ist dabei der Typ des Terms ( ${}v_{1},\ldots ,v_{n}$ ).
f: ist der Funktionsname
$v_{1},...,v_{n}$ ist ein formaler Parameter
$t(v_{1},...,v_{n})$ : ist ein Funktionsausdruck

Beispiel

$f(p,q,x,y):=if~(p\lor q)~then~2x+1~else~3y-1$
$g(x):=~if~even(x)~then~x/2~else~3x-1$
$h(p,q):=~if~p~then~q~else~false$

Jede Funktionsdefinition hat das Schema Funktionsname(formale Parameter):= Funktionsausdruck

Signatur einer Funktion

Eine Funktion f hat die folgende Funktionsdefinition:

$f(v_{1},...,v_{n}):=t(v_{1},...,v_{n})$

mit $v_{1},...,v_{n}$ sind vom Typ $T_{1},...,T_{n}$

$t(v_{1},...,v_{n})$ ist vom Typ T

Die Signatur von f ist: $f:T_{1}*...*T_{n}\to T$ mit der Struktur

Name mit Stelligkeit: Parameter mit Typ * ... * Parameter mit Typ → Typ des Rückgabewertes

Beispiel einer Funktionsdefinition

f(p,q,x,y) := if (p ∨ q) then 2x + 1 else 3y ‐1

g(x) := if even(x) then x / 2 else 3x ‐1

h(p,q) := if p then q else false, mit h als Funktionsname, (p,q) als formalen Parameter und dem darauffolgenden Funktionsausdruck.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.2 zu finden.