Fixpunkt-Kombinator

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

<math>x = f(x)</math>

und somit

<math>\hat y f = x. </math>

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

<math> \hat y\ f = f\ (\hat y\ f). </math>

Spezielle Fixpunkt-Kombinatoren

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

<math>\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))</math>

Fixpunkt-Kombinatoren werden in verschiedenen Bereichen eingesetzt:

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