Fixpunkt-Kombinator

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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

${\displaystyle x=f(x)}$

und somit

${\displaystyle {\hat {y}}f=x.}$

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

${\displaystyle {\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:

${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

Fixpunkt-Kombinatoren werden in verschiedenen Bereichen eingesetzt:

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