Funktionen höherer Ordnung

Bemerkung

Hier geht das funktionale Programmieren eigentlich erst los. Alles davor war nur zur Gewöhnung an die Syntax von Haskell und die Bedienung von Hugs.

Die Programme hätte man in Pascal, C, Java etc. recht ähnlich schreiben können (etwas länger wären sie zwar, aber nicht so sehr verschieden).

Ab jetzt ziehen wir aber wirklich an diesen Sprachen vorbei, weil bei uns Funktionen ganz normale Daten sind, das heißt, sie können sowohl Argument als auch Ergebnis von anderen Funktionen sein.

Übung: wieweit geht das in den genannten Sprachen, bzw. wie müßte man das simulieren?

map

Wir hatten bei Mergesort die Funktion "einzelne":
einzelne :: [a] -> [[a]]
einzelne xs = [ [x] | x <- xs ]
Wir tun für heute mal so, als ob wir keine List Comprehensions hätten. Dann müßten wir schreiben
einzelne [] = []
einzelne (x : xs) = [x] : einzelne xs
Nächstes Beispiel: wir wollen in einer Zeichenkette alle Klein- in Großbuchstaben umwandeln.
um :: [ Char ] -> [ Char ]
um [] = []
um (c : cs) = 
   ( if isLower c then toUpper c else c) : um cs

Beide Funktionen zeigen ein ganz einfaches Rekursionsschema über Listen: eine Funktion wird elementweise angewandt. Die einzelnen Rechnungen sind unabhängig voneinander. Dieses Schema heißt "map":

map f [] = []
map f (x : xs) = f x : map f xs
und die Beispiele schreiben wir so
einzelne xs = map unit xs  where  unit x = [x]
um       cs = map hoch cs  where  hoch c = if isLower c then toUpper c else c

Welchen Typ hat "map"? Es bekommt zwei Argumente, das erste ist eine Funktion "f : a -> b", das zweite ein Liste von a, und das Ergebnis ist eine Liste von b.

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

best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de