Fixpunkt-Kombinator

Vorlage:Belege Ein Fixpunkt-Kombinator ist ein mathematischer Operator in Form einer Funktion höherer Ordnung $\hat{y}$, welcher von einer Funktion $f$ einen ihrer Fixpunkte liefert. Ein Fixpunkt $x$ der Funktion $f$ erfüllt die Bedingung

$x=f(x)$

und somit

$\hat{y}f=x.$

Durch Einsetzen ergibt sich die Eigenschaft des Fixpunkt-Kombinators dann als

$\hat{y}f=f(\hat{y}f).$

Spezielle Fixpunkt-Kombinatoren

Ein spezieller Fixpunkt-Kombinator ist der von Haskell Curry beschriebene Y-Kombinator des Lambda-Kalküls:

$\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$

Fixpunkt-Kombinatoren werden in verschiedenen Bereichen eingesetzt:

• im untypisierten und im typisierten Lambda-Kalkül,
• in der funktionalen Programmierung
• und in der imperativen Programmierung.