TU Wien:Funktionale Programmierung VU (Knoop)/Allgemeinen Typ eines Lambda-Ausdrucks bestimmen (Howto t2-Beispiele)

Aus VoWi
Zur Navigation springen Zur Suche springen

Den allgemeinen Typ einer Lambda-Funktion (anonymen Funktion) bilden, ist ein quasi fixer Bestandteil der Prüfung und kommt in Aufgabe 1 unter dem Namen t2 immer wieder vor. Zuerst sollte man allerdings verstehen, was ein Lambda-Ausdruck eigentlich ist und was dieser macht. Dies ist sehr gut in folgendem Dokument erklärt: Datei:TU Wien-Funktionale Programmierung VU (Knoop) - Lambda Expressions.pdf

Die Lösung dieser Beispiele ist nicht auf Anhieb intuitiv, hat man allerdings folgendes Kochrezept verinnerlicht, sollte es nicht so schwierig sein.

  1. Hinter welchen Argumenten verbergen sich Funktionen, hinter welchen Konstanten?
  2. In welcher Reihenfolge werden Funktionen abgearbeitet bzw. wie sind diese miteinander verkettet?
  3. Was ist die Eingabe?
  4. Was ist die Ausgabe/der "Rückgabewert"?

Wir werden nun anhand eines Beispiels versuchen, diese Fragen für dieses zu beantworten und dabei versuchen ein Schema zu entwickeln, das generell bei diesen Beispielen hilft:

Beispiel 1[Bearbeiten | Quelltext bearbeiten]

t2 = (\x y z a -> y(z(z(a))))

Wir müssen hier zwischen der linken und der rechten Seite unterscheiden, wobei der Pfeil hier die zwei Seiten voneinander trennt. Auf der linken Seite stehen die Argumente, auf der rechten wie diese vom Lambda-Ausdruck verwendet werden.

Gemäß unserem Kochrezept, ermitteln wir nun, hinter welchen Argumenten Funktionen stecken und hinter welchen Konstanten.

  • x wird auf der rechten Seite nicht verwendet, es handelt sich also um eine Konstante.
  • y ist eine Funktion.
  • z ist eine Funktion.
  • a ist eine Konstante.

Wie sind Funktionen miteinander verkettet?

  • Konstante a wird der Funktion z übergeben, das Ergebnis wird wiederum z übergeben und dieses Ergebnis wird an y übergeben.

Aus diesen Informationen können wir uns nun folgendes Schema ableiten:

_ -> ( _ -> _ ) -> ( _ -> _ ) -> _ -> _
x         y             z        a    Resultat

Eine Konstante kommt immer einstellig vor, da diese nichts erzeugt. Eine Funktion führt aber immer einen Typ in einen anderen über und muss deshalb zweistellig in der Form _ -> _ vorkommen. Nicht vergessen darf man auch das Resultat, sowie die Eingabe, falls diese nicht explizit angegeben wurde. In diesem Beispiel ist sie mit a allerdings explizit als Argument angeführt.

Nun setzen wir in das Schema Buchstaben ein, wobei jeder Buchstabe für einen eigenen, spezifischen Typ steht:

Für x beginnen wir einfach bei a. Da x eine unbenutzte Konstante ist, wird der Typ a sonst nirgends vorkommen und darf sonst auch nicht verwendet werden.

Für y nehmen wir die nächsten zwei freien Buchstaben b -> c. Nun wissen wir, dass das Resultat des Lambda-Ausdrucks von der Funktion y bestimmt wird. Daher benützen wir c nicht nur für y sondern auch für das Resultat:

x -> (b -> c) -> ( _ -> _ ) -> _ -> c
x        y            z        a    Resultat

Nun überlegen wir uns, welchen Typ die Funktion z entgegennimmt, und wer diesen erwartet. Das Resultat von z wird als Argument für y verwendet, also müssen wir für die Ausgabe von z auch b verwenden. Da z auch wieder auf z angewendet wird, muss die Eingabe und die Ausgabe vom gleichen Typ, also auch b sein. Beim ersten Aufruf wird z mit a aufgerufen. Wir wissen, dass z Werte vom Typ b erwartet, also muss a auch vom Typ b sein.

Somit ergibt sich:

x -> (b -> c) -> (b -> b) -> b -> c
x        y           z       a    Resultat

Dies lässt sich auch leicht in Hugs nachprüfen:

Hugs> :t  (\x y z a -> y(z(z(a))))
\x y z a -> y (z (z a)) :: a -> (b -> c) -> (b -> b) -> b -> c

Beispiel 2[Bearbeiten | Quelltext bearbeiten]

t2 = (\x y z -> y.x.y)

Wendet man das Schema von oben schrittweise an, bekommt man zuerst folgendes Template. Zu beachten ist, dass z eine Konstante ist, die nicht verwendet wird, wir aber trotzdem implizit ein Eingabeargument haben, das es zu berücksichtigen gilt.

(_ -> _) -> (_ -> _) -> _ -> _       -> _
    x           y       z  Eingabe      Resultat

Fangen wir ganz einfach mit x. Diese Funktion nimmt etwas entgegen, und produziert etwas.

(a -> b) -> (_ -> _) -> _ -> _       -> _
    x           y       z  Eingabe      Resultat

Nun wissen wir, dass x den Wert von y übernimmt und auch wieder an y übergibt. Das heißt, y muss also den Typ a erzeugen, und den Typ b entgegennehmen:

(a -> b) -> (b -> a) -> _ -> _       -> _
    x           y       z    Eingabe    Resultat

Unserem unbenutzten z weisen wir nun c, da dies noch nicht verwendet wurde:

(a -> b) -> (b -> a) -> c -> _       -> _
    x           y       z    Eingabe    Resultat

Die erste Funktion, die aufgerufen wird, ist y. Diese haben wir bereits als b -> a definiert. Deshalb ist der Typ der Eingabe nun ebenfalls b. Die letzte Funktion, die aufgerufen wird, ist ebenfalls y. Diese produziert etwas vom Typ a.

Dadurch ergibt sich nun:

(a -> b) -> (b -> a) -> c -> b       -> a
    x           y       z    Eingabe    Resultat

Beispiel 3[Bearbeiten | Quelltext bearbeiten]

t2 = (\z -> \y -> \x -> z.y.x)

Hier muss man wissen, dass der Ausdruck identisch ist zu:

t2 = (\z y x -> z.y.x)

Womit sich auch wieder das übliche Schema anwenden lässt. Wichtig ist hier, dass die Eingabe wieder implizit gegeben ist.