Listen in Haskell
Übersicht: Listen in Haskell
Allgemeines
Diese Seminararbeit soll Beispiele für die Programierung mit Haskell-Listen zeigen und dabei insbesondere die Möglichkeiten des Typensystems und der Polymorphie in Haskell, die Ausdruckskraft des sprachintegrierten Listenkonzeptes sowie die Flexibilität des Einsatzes von Funktionen als Parameter deutlich machen.
Das integrierte Listenkonstrukt ist ein wesentlicher Bestandteil der Programmiersprache Haskell, das auf syntaktisch einfache Weise die Modellierung von mehrwertigen Datenstrukturen ermöglicht und die Ausdruckskraft der Sprache beträchtlich erhöht. Bemerkenswert dabei ist, daß die Integration in die Sprache selbst kaum über das Typensystem hinausgeht - die Masse der notwendigen Festlegungen wurde in Haskell selbst formuliert, in die Prelude-Bibliothek ausgelagert und gehört somit nicht zum Kernumfang der Sprache bzw. zu den Schlüsselwörtern/symbolen.
Im nachfolgenden soll kurz zusammengefaßt werden, was es zum Umgang mit Haskell-Listen zu wissen gibt. Dieses setzt sich zusammen aus der allgemeinen Syntax, den Eigenschaften der Listen und den vordefinierten Funktionen, die auf Listen arbeiten.
Haskell-Listen...
- sind getypt, es können lediglich Elemente eines Typs in einer Liste vorkommen (Mischen von Typen ist nicht möglich). Dies ergänzt sich mit Tupeln: Listen sind theoretisch beliebig lange Folgen von Elementen eines Typs, Tupel sind definiert lange Folgen von Elementen, die verschiedene Typen haben können. Typsignatur von Listen: z.B. [Int], [Char], usw.
- können polymorph sein, d.h., der Typ einer Liste kann parametrisiert werden. Typsignatur in diesem Fall: z.B. [a]
- können per Aufzählung der Elemente definiert werden (Beispiel: [1,2,3]) oder mittels des Listenkonstruktors (Beispiel: 1:(2:(3)) ).
- werden per Rekursion (x:xs beschreibt das erste Element x einer Liste und die Restliste xs) oder per Indizierung (Operator !!) verarbeitet (die Indizierung beginnt bei 0)
- können mittels Erzeugungsschemata beschrieben werden (list comprehensions): z.B. [ transform neueListe | neueListe <- alteListe, tollerTest neueListe ], in dem die Elemente einer existierenden Liste traversiert, optional mit Prädikaten gefiltert und ebenfalls optional durch weitere Funktionen transformiert in eine neue Liste übernommen werden. In diese Rubrik fällt auch eine abgekürzte Schreibweise für Aufzählungen: z.B. [1..10] um eine Liste mit Elementen von 1 bis 10 zu erzeugen.
- können dank Haskell´s Lazy Evaluation Strategie unendlich lang sein (ihrer Beschreibung nach), wie z.B. bei [1..]. Solche Listen können verwendet werden, solange für den gewünschten Zweck die Auswertung nur eines Teils der Liste ausreicht.
Wichtige Funktionen
fold
Signatur: foldl :: (a -> b -> a) -> a -> [b] -> a, foldr :: (a -> b -> b) -> b -> [a] -> b
Semantik: "Falten" von Listen mit einer binären Funktion, linksassoziativ bzw. rechtsassoziativ. Ein initiales Element von einem Typ 1 wird über die Funktion mit einem Listenelement vom Typ 2 verknüpft zu einem Ergebnis vom Typ 1, mit dem der Vorgang mit dem nächsten Listenelement wiederholt wird. Im Endeffekt entsteht ein Wert des Ergebnistyps der Faltungs-Funktion.
Beispiel: foldr (+) 0 [1,2,3] == 6
scan
Signatur: scanl :: (a -> b -> a) -> a -> [b] -> [a], scanr :: (a -> b -> b) -> b -> [a] -> [b]
Semantik: "Falten" von Listen unter Erzeugung einer Liste mit allen Zwischenergebnissen (Falten aller Teillisten), linksassoziativ bzw. rechtsassoziativ.
Beispiel: scanl (+) 0 [1,2,3] == [0,1,3,6]
map
Signatur: map :: (a -> b) -> [a] -> [b]
Semantik: Anwenden einer Funktion auf alle Elemente einer Liste (Erzeugen einer neuen Liste durch Anwenden einer Funktion auf alle Elemente einer existierenden Liste).
Beispiel: map (+1) [1..5] == [2,3,4,5,6]
filter
Signatur: filter :: (a -> Bool) -> [a] -> [a]
Semantik: Filtern einer Liste mit einem Prädikat, Erzeugen einer neuen Liste mit allen Elementen einer existierenden Liste, die das Prädikat erfüllen
Beispiel: filter (>5) [1..10] == [6,7,8,9,10]
zip
Signatur: zip :: [a] -> [b] -> [(a,b)]
Semantik: Kombinieren von zwei Listen zu einer neuen Liste, die die korrespondierenden Elemente der Ausgangslisten als Tupel enthält. Die neue Liste hat die Länge der kleineren Ausgangsliste (überzählige Elemente der längeren Ausgangsliste werden ignoriert).
Beispiel: zip [1,3] [2,4] == [(1,2),(3,4)]
zipWith
Signatur: zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Semantik: wie zip, zur Erzeugung der neuen Liste wird jedoch statt eines Tupel-Konstruktors eine beliebige (per Parameter anzugebene) Funktion auf die korrespondierenden Listenelemente angewendet.
Beispiel: zipWith (+) [1,2,3] [3,2,1] == [4,4,4]
takeWhile, dropWhile
Signatur: takeWhile, dropWhile :: (a -> Bool) -> [a] -> [a]
Semantik: Erzeugen einer neuen Liste aus allen führenden Elementen einer Ausgangsliste, die ein Prädikat erfüllen, bzw. mit allen Elementen nach den führenden Elementen, die das Prädikat erfüllen.
Beispiel: takeWhile (<=5) [1..10] == [1,2,3,4,5]
dropWhile (<=5) [1..10] == [6,7,8,9,10]
take, drop
Signatur: take, drop :: Int -> [a] -> [a]
Semantik: Erzeugen einer Liste mit den n führenden Elementen einer Ausgangsliste bzw. mit den Elementen nach den n führenden Elementen.
Beispiel: take 5 [1..10] == [1,2,3,4,5]
drop 5 [1..10] == [6,7,8,9,10]
reverse
Signatur: reverse :: [a] -> [a]
Semantik: Erzeugen einer Liste mit den Elementen einer Ausgangsliste in umgekehrter Reihenfolge.
Beispiel: reverse [1..10] == [10,9,8,7,6,5,4,3,2,1]
Konkatenation ++
Signatur: (++) :: [a] -> [a] -> [a]
Semantik: Erzeugen einer neuen Liste aus den Elementen von zwei Ausgangslisten. Die Reihenfolgen bleibt erhalten.
Beispiel: (++) [1,2] [3,4] == [1,2,3,4]
replicate
Signatur: replicate :: Int -> a -> [a]
Semantik: Erzeugen einer Liste von n Elementen, die einem Parameterelement entsprechen.
Beispiel: replicate 10 ´.´ == ".........."
Indizierung !!
Signatur: (!!) :: [a] -> Int -> a
Semantik: Indizierter Zugriff auf eine Liste, beginnend mit Index 0
Beispiel: [1,2,3,4] !! 1 == 2
Code generated with AusarbeitungGenerator Version 1.1, weblink