www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

j3ssi

Gepostet:
10.03.2011 14:07

Erkennen von Typen ( Lambda Kalkül)  
Hallo zusammen hab hier ne Aufgabe wo ich nicht wirklich weiss wie man auf die Lösung kommt und zwar :

Geben sie den Typ an von:

map (\f -> (3 * (f 5)))


Der Typ von Map und f müsste so sein :

map :: (a -> b) -> [a] ->
f :: (Integer -> Integer) -> Integer


Laut ghci ist der Typ von


map (\f -> (3 * (f 5))) :: [Integer -> Integer] -> [Integer]


Wie kommt man auf diese Lösung ohne ghci zur Verfügung zu haben
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
11.03.2011 18:24

   
Hallo,

du leitest dir den Typ anhand der einzelnen Teilausdrücke her. Diese sind gegeben:
map :: (t -> s) -> [t] -> [s]
3, 5 :: Integer
* :: Integer -> Integer -> Integer

Dann fängst du innen an. f wird auf ein Argument vom Typ Integer angewendet, f hat also den Typ Integer -> a (a ist noch nicht bekannt). Dann wird das ganze mit 3 multipliziert. Aus dem Typ von * folgt somit, dass f 5 auch den Typ Integer haben muss, f also Integer -> Integer. Da wir nun den Typ von f kennen, kennen wir auch den des gesamten Lambda-Ausdrucks: (Integer -> Integer) -> Integer. Bekommt also die Funktion f und liefert ein Integer.

Das ganze wird nun auf den Typ des ersten Arguments von map gematcht (genauer: beide werden unifiziert): (t -> s) ~ (Integer -> Integer) -> Integer, das ergibt t = (Integer -> Integer) und s = Integer. Damit kannst du den Typ von map komplettieren zu (Integer -> Integer -> Integer) -> [Integer -> Integer] -> [Integer]. Da map bereits auf ein erstes Argument angewendet wurde, fällt dieses im Typ weg und es bleibt [Integer -> Integer] -> [Integer], also genau der vom GHCi ermittelte Typ.

Im Prinzip erfolgt die Typherleitung des gesamten Ausdrucks durch Unifizierung der Typen der Teilausdrücke miteinander; Typvariablen werden durch konkretere Typen ersetzt, z.B. t durch Integer -> Integer.


Viele Grüße,

Siracusa
Zum Seitenanfang