Um diesen Mangel zu beheben, gestatten wir polymorphe (wörtlich übersetzt: vielgestaltige) Ausdrücke. Diese haben polymorphe Typen. Solche entstehen durch (eventuell mehrfache) Typ-Konstruktor-Anwendung aus Grundtypen und Typvariablen. Dabei denken wir uns die Typvariablen ganz außen universell quantifiziert. Eine Deklaration "length :: [a] -> Int" lesen wir so: "forall a in Typ: length :: [a] -> Int".
(Bemerkung: das ist tatsächlich eine Einschränkung: wir könnten uns auch lokale Quantoren wünschen, und auch existentielle Quantoren. Sowohl ghc als auch hugs implementieren einiges derart. Das führt jedoch hier zu weit. Schade.)
Ein polymorphes Typsystem gestattet dem Programmierer größere Freiheiten. Es entsteht andererseits ganz natürlich: wo kommt denn die Polymorphie her? Die Datentyp-Konstruktoren selbst sind oft polymorph! Beispiel Listen: wir haben "[] :: [a]" und "(:) :: a -> [a] -> [a]". Trotzdem sollen günstige Eigenschaften des einfachen Typsystems erhalten bleiben: es gibt keine Laufzeitfehler, und der Compiler soll mit Typen rechnen können. Nun hat jeder polymorphe Ausdruck viele Typen, aber das System ist so gebaut, daß genau einer davon alle anderen als Instanzen enthält. Das ist der "allgemeinste" Typ des Ausdrucks (principal type), und diesen kann der Compiler ausrechnen (wieder wie vorhin ohne Hilfe des Programmierers).
Aufgabe: bestimme die prinzipiellen Typen von "map . map" und "map map".
Anleitung: schreibe jeweils einen Ausdruck, in dem die fraglichen Teile vorkommen, und den man auswerten kann.
Beispiel: was kann man mit "map . map" machen? Wir haben "(map . map) f = map (map f)". Wenn "f :: a -> b", dann "map f :: [a] -> [b]" und deswegen "map (map f) :: [[a]] -> [[b]]". Also ist "map . map :: (a -> b) -> ([[a]] -> [[b]])". Beispielsweise geht "(map . map) (+1) [[0,1],[2]]".
Führe diese Untersuchung für "map map" durch.