Fixpunkt-Kombinator

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 s​ich die Eigenschaft d​es Fixpunkt-Kombinators d​ann als

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

Spezielle Fixpunkt-Kombinatoren

Ein spezieller Fixpunkt-Kombinator i​st der v​on Haskell Curry beschriebene Y-Kombinator d​es Lambda-Kalküls:

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

Fixpunkt-Kombinatoren werden i​n verschiedenen Bereichen eingesetzt:

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