Funktionale Programmierung mit Haskell/ Funktionen auf Listen
Listen werden in eckigen Klammern angegeben und durch Kommas getrennt, z.B. [1,2,3]. Sie sind geordnet und können nur Daten eines Typs enthalten. Listen können leer sein: []. Die verkürzte Schreibweise [1..5] wird von Haskell als [1,2,3,4,5] interpretiert. Listenverarbeitung ist eine der Stärken von Haskell.
Einfache Funktionen auf Listen[Bearbeiten]
Im unten stehenden Kasten sind einige essentielle Funktionen auf Listen dargestellt. Manche dieser Funktionen liegen nicht im Modul Prelude, sondern im Modul Data.List; dann ist es nötig, den Modulnamen anzugeben. Manche der gewünschten Ergebnisse lassen sich auf verschiedene Weise erreichen, z.B. lässt sich die Kombination nub und ++ durch union ersetzen. Diese funktionalen Überschneidungen sind in Haskell durchaus gewünscht und helfen dem geübten Programmierer, sehr kompakten und gut verständlichen Code zu schreiben.
Bei den Beispielen wird erstmals der Dollar-Operator $ genutzt. Er wendet den Befehl links vom $ an auf den Wert, der rechts davon ermittelt wurde. Auf diese Weise lassen sich also Funktionen konkatenieren.
Prelude> head ["Hase", "Pferd", "Kuh"] -- Ermittlung des ersten Wert aus einer Liste
"Hase"
Prelude> tail ["Hase", "Pferd", "Kuh"] -- Ermittlung aller Werte außer den ersten aus einer Liste
"Pferd", "Kuh"
Prelude> last ["Hase", "Pferd", "Kuh"] -- Ermittlung des letzten Wert aus einer Liste
"Kuh"
Prelude> length ["Hase", "Pferd", "Kuh"] -- Länge einer Liste
3
Prelude> [1..5] -- Erzeugung einer Liste von eins bis fünf
[1,2,3,4,5]
Prelude> [1..5]!!3 -- aus dieser Liste wird der dritte Wert geholt (die Zählung beginnt bei Null)
4
Prelude> [3,6..20] -- Erzeugung einer Liste aller durch drei teilbarer Zahlen unter zwanzig
[3,6,9,12,15,18]
Prelude> [10,8..0] -- Erzeugung einer Liste, die in Zweierschritten kleiner wird
[10,8,6,4,2,0]
Prelude> [10,8..(-10)] -- Das geht auch in den negativen Bereich hinein
[10,8,6,4,2,0,-2,-4,-6,-8,-10]
Prelude> [1..10] ++ [8..12] -- Konkatenieren von Listen mit ++
[1,2,3,4,5,6,7,8,9,10,8,9,10,11,12]
Prelude> Data.List.nub $ [1..10] ++ [8..12] -- Löschung doppelter Einträge aus einer Liste
[1,2,3,4,5,6,7,8,9,10,11,12]
Prelude> Data.List.union [1..10] [8..12] -- Vereinigen von zwei Listen mit dem union-Befehl
[1,2,3,4,5,6,7,8,9,10,11,12]
Prelude> (Data.List.union [1..10] [8..12]) == (Data.List.nub $[1..10]++ [8..12]) -- Der union-Befehl macht das Gleiche wie ++ und nub zusammen
True
Prelude> maximum $ [11..15] ++ [3..12] -- Ermittlung des Maximum aus einer konkatenierten Liste
15
Prelude> Data.List.sort $ Data.List.union [11..15] [3..12] -- Sortierung von Listen
[3,4,5,6,7,8,9,10,11,12,13,14,15]
Prelude> take 5 $ [3..12] -- Ermittlung der ersten fünf Elemente aus einer Liste
[3,4,5,6,7]
Prelude>sum $ take 5 $ [3..12] -- Aufsummierung der ermittelten fünf Werte
25
Prelude>product [3,4,9] -- Multiplikation einer ganze Liste
108
Prelude> zip [11..15] [3..12] -- zip verbindet Listen paarweise zu Tupeln, bis die kürzere Liste endet
[(11,3),(12,4),(13,5),(14,6),(15,7)]
Prelude>Data.List.intersect [11..15] [3..12] -- Bilden der Schnittmenge von zwei Listen
[11,12]
Prelude>Data.List.insert 17 [10,12..20] -- Einfügen eines Elements an die richtige Stelle
[10,12,14,16,17,18,20]
Prelude> replicate 5 6 -- auch mit replicate können Listen gebildet werden
[6,6,6,6,6]
Prelude> replicate 5 [4,5,6] -- Eine Liste in einer Liste
[[4,5,6],[4,5,6],[4,5,6],[4,5,6],[4,5,6]]
Prelude>Data.List.permutations [1,2,3] -- Eine Liste aus allen Permutationen von 1,2 und 3
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
Prelude>maximum $ Data.List.permutations [1,2,3] -- interessant!
[3,2,1]
Prelude>let ff = [7,9..17]++ [5,10..40] -- Zuweisung einer Liste an eine Variable
Prelude>ff -- Zeigt den Wert der Variablen an
[7,9,11,13,15,17,5,10,15,20,25,30,35,40]
Prelude>reverse ff -- reverse dreht die Liste um
[40,35,30,25,20,15,10,5,17,15,13,11,9,7]
Prelude> drop 8 ff -— drop 8 Wirft die ersten acht Werte weg
[15,20,25,30,35,40]
Prelude>drop 8 "Hello World" -- Strings sind auch Listen daher lassen sich alle Listenbefehle auf Strings anwenden
"rld"
Prelude>reverse "Hello World" -- Strings sind auch Listen daher lassen sich alle Listenbefehle auf Strings anwenden
"dlroW olleH"
Prelude>Data.List.sort "Hello World" -- Strings sind auch Listen daher lassen sich alle Listenbefehle auf Strings anwenden
" HWdellloor"
Prelude> filter (>10) [2..17] -- Filtern von Werten aus Listen
[11,12,13,14,15,16,17]
Prelude> -- diese Eingaben führen zu Fehlermeldungen:
Prelude>["Hase", 3] -- unterschiedliche Typen in einer Liste sind nicht erlaubt
Prelude>[1..5]!!7 -- bei fünf Listenelementen gibt es kein siebtes Element
Prelude>[]!!0 -- aus einer leeren Liste kann man kein Element herausholen
Prelude>repeat 9 -- So wird eine unendliche Liste erzeugt
Prelude>
any, all und elem[Bearbeiten]
Zur weiteren Vertiefung erhalten die Funktionen any, all und elem ein eigenes Kapitel. elem unterscheidet sich von den anderen Funktionen, da im ersten Parameter kein Wahrheitswert ermittelt wird, sondern nur ein Listenelement angegeben wird. In diesen Beispielen wird auch die Infix-Notation verwendet, sowie eine überraschende Möglichkeit der Klammerung:
Prelude> any (>=4) [3..7] -- sind einige der Listenelemente größer gleich 4?
True
Prelude> all (>=4) [3..7] -- sind alle Listenelemente größer gleich 4? Hier: Nein
False
Prelude> all (>=4) [9..17] -- sind alle Listenelemente größer gleich 4? Hier: Ja
True
Prelude> all (odd) [9,11..17] -- sind alle Listenelemente ungerade? Hier: Ja
True
Prelude> elem 13 [9,11..17] -- ist die Zahl 13 in der Liste? Hier: Ja
True
Prelude> 'e' `elem` "Haskell" -- ist ein e im String (Abfrage mit Infix-Notation)? Hier: Ja
True
Prelude> elem 'e' "Haskell" -- ist ein e im String (Abfrage mit Präfix-Notation)? Hier: Ja
True
Prelude> any (=='e') "Haskell" -- ist ein e im String (Abfrage mit any statt mit elem)? Hier: Ja
True
Prelude> all (=='e') "Haskell" -- sind alle Buchstaben im String e's? Hier: Nein
False
Prelude> (all (=='e')) "Haskell" -- Diese Klammerung ist ungewöhnlich, aber möglich
False
Prelude> (any (=='e')) "Haskell" -- Diese Klammerung ist ungewöhnlich, aber möglich
True
Prelude> any (=="22") ["11","22","33","44","55","66"] -- any mit einer Liste von Strings
True
Prelude> elem "22" ["11","22","33","44","55","66"] -- elem mit einer Liste von Strings
True
Prelude> all (>"01") ["11","22","33","44","55","66"] -- all mit einer Liste von Strings
True
Prelude> all (>"21") ["11","22","33","44","55","66"] -- all mit einer Liste von Strings
False
Prelude>
List Comprehension[Bearbeiten]
Einfache Listen werden also mit eckigen Klammern erzeugt: [1..20]. Viele Anwendungen benötigen aber sehr komplexe Listen. List Comprehension ist eine einfache Möglichkeit, solche Listen zu erzeugen. Die Form der List comprehension ist: [ausdruck|kriterium1,kriterium2,..kriteriumn]. Im Ausdruck werden Variablen erzeugt, in den Kriterien werden Listen erzeugt, Filter definiert oder Zuweisungen vorgenommen.
Hier ein paar Anwendungsbeispiele:
Prelude> [x|x<-[1..10]] -- Sehr einfache list comprehension
[1,2,3,4,5,6,7,8,9,10]
Prelude> [x | x<-[1..20], x >= 10] -- Erzeugt eine Liste von 1 bis 20 und filtert die Werte kleiner 10 aus
[10,11,12,13,14,15,16,17,18,19,20]
Prelude> [x*2 | x <- [10,3,22,2,17,9,10], x >= 10] -- filtert die Werte kleiner 10 aus der Liste und verdoppelt die Elemente im Ergebnis
[20,44,34,20]
Prelude> [(x,y)|x<-[1..24], y<-[1..24], x*y==24] -- Findet alle Zahlenpaare, deren Multiplikation 24 ergibt
[(1,24),(2,12),(3,8),(4,6),(6,4),(8,3),(12,2),(24,1)]
Prelude> [x|x<- [1..100], x `mod` 7 == 0] -- Findet alle durch 7 teilbaren Zahlen bis hundert
[7,14,21,28,35,42,49,56,63,70,77,84,91,98]
Prelude> [Data.Char.toUpper x | x<-"Hello World!"] -- wandelt einen String (also eine Liste von Char) in Großbuchstaben um
"HELLO WORLD!"
Prelude> sum [x | x <- [1..999], x `mod` 3 == 0 | x `mod` 5 == 0] -- Addiere alle Zahlen unter 1000, die sich durch 3 oder 5 teilen lassen'"`UNIQ--ref-00000006-QINU`"'
233168
Prelude>
Listen als rekursive Strukturen[Bearbeiten]
Die oben dargestellte Darstellungsweise von Listen mit eckigen Klammern und Kommata als Listentrenner ist eigentlich nur syntaktischer Zucker. Streng genommen ist eine Liste (wie fast alles in Haskell) rekursiv definiert:
Eine Liste ist entweder ein leeres Element oder sie besteht aus einem Element, gefolgt von einem Doppelpunkt und einer Liste.
Somit kann eine Liste beliebig lang sein, aber die Listenelemente sind stets mit einem Doppelpunkt getrennt, und irgendwann erscheint eine leere Liste, die das Ende der Liste markiert. In Haskell-Notation bedeutet das:
Prelude>let a=[] -- die leere Liste
Prelude> a
[]
Prelude>let a=1:[] -- eine 1, gefolgt von einem Doppelpunkt und einer leeren Liste
Prelude> a
[1]
Prelude> let a=1:2:3:4:[] -- eine 1, gefolgt von einem Doppelpunkt und einer nichtleeren Liste
Prelude> a
[1,2,3,4]
Prelude>
Der Doppelpunkt als Listentrenner[Bearbeiten]
Die Listennotationen mit Kommas und mit Doppelpunkt können auch kombiniert verwendet werden:
Prelude> 12:[13..15] -- Fügt vorne eine 12 ein
[12,13,14,15]
Prelude> it ++ 33:32:31:[] -- Fügt hinten drei Zahlen ein
[0,1,2,33,32,31]
Prelude> 'a':['b', 'c', 'd', 'e'] -- Funktioniert z.B auch bei Strings
"abcde"
Prelude>
In den Beispielen der folgenden Kapitel wird der Doppelpunkt-Operator genau in diesem Sinne eingesetzt.
Eigene Listenfunktionen erstellen[Bearbeiten]
Hier erstellen wir selbst Listenfunktionen. Zuerst bauen wir die oben gezeigte Funktion head nach und nennen sie erstes. Dazu benötigen wir auch den Doppelpunkt als Listentrenner:
-- Liefert das erste Element einer Liste
erstes [] = []
erstes (anfang:rest) = [anfang]
Die erste Codezeile besagt: Wenn erstes mit einer leeren Liste als Parameter aufgerufen wird, soll es auch eine leere Liste zurückgeben. Da eine Liste immer mit einer leeren Liste endet, ist dies ein sicheres Signal für das Rekursende.
In der zweiten Codezeile steht anfang für das erste Element der übergebenen Liste, und rest für die übrigen Elemente der Liste. Falls die übergebene Liste nur ein Element besitzt, ist rest die leere Liste. Diese Zeile sagt: Wenn erstes mit einer nichtleeren Liste als Parameter aufgerufen wird, soll es das erste Element der Liste zurückgeben.
In der sonstigen Literatur zu Haskell findet man die Schreibweise x:xs statt anfang:rest. Wir wollen uns dieser Schreibweise in Zukunft anschließen, aber darauf hinweisen, dass es auf den Namen nicht ankommt. Man liest so etwas als x, an dem viele xe[2] angehängt sind.
$> ghci erstes.hs
...Ok, modules loaded: Main.
*Main> erstes ["Hase", "Igel", "Pferd"] -- Eine Liste mit Strings
["Hase"]
*Main> erstes [5,9,1] -- Eine Liste mit Zahlen
[5]
*Main> erstes [True, False, True, False] -- Eine Liste mit boolschen Werten
[True]
*Main> erstes "Hallo Welt" -- Ein String
"H"
*Main> erstes [] -- eine leere Liste
[]
Wie Sie sehen, funktioniert dieses kleine Programm nicht nur mit Listen von Zahlen, sondern mit jeder Art von Listeninhalten, ohne dass wir etwas dafür tun mussten.
Im zweiten Beispiel erstellen wir eine Funktion, die stets das zweite Listenelement liefert. Bei leeren Listen oder bei Listen mit nur einem Element wird wieder die leere Liste zurückgeliefert. Dazu schreiben wir folgenden Code in die Datei zweites.hs:
-- Liefert das zweite Element einer Liste
zweites [] = []
zweites [a] = []
zweites (a:b:xs) = [b]
Die meisten Anweisungen kennen Sie schon aus dem ersten Beispiel: Bei einer leeren Liste: gib eine leere Liste zurück. Bei einer Liste mit einem Element: Gib eine leere Liste zurück.
Bei einer Liste, die mindestens zwei Elemente besitzt (also a, b und einen Rest namens xs, der auch leer sein kann): Gib das zweite Listenelement zurück. Das Ganze sieht zur Laufzeit so aus:
$>ghci zweites.hs
...Ok, modules loaded: Main.
*Main>zweites []
[]
*Main>zweites [4.5]
[]
*Main>zweites [4.5, 8.4, 7.8, 9.0, 6.7]
[8.4]
An diesem Beispiel sollte Sie nichts mehr überraschen.
Das dritte Beispiel ist eine Funktion, die das letzte Listenelement liefert:
-- Liefert das letzte Element einer Liste
letztes [] = []
letztes [x] = [x]
letztes (x:xs) = letztes xs
Eine leere Liste als Argument liefert wieder eine leere Liste als Ergebnis zurück. Eine Liste mit einem Element liefert dieses Element.
In der letzten Zeile haben wir eine Rekursion. Sie besagt: Wenn eine Liste mehr als ein Element besitzt, suche das letzte Element der "Restliste" xs. Dadurch ruft sich die Funktion letztes so lange selbst auf, bis die Restliste nur noch aus einem Element besteht. Dieses Element wird dann durch die Zeile 2 als Ergebnis geliefert:
$>'ghci letztes.hs
...Ok, modules loaded: Main.
*Main>letztes []
[]
*Main>letztes [8,9,10]
[10]
*Main>letztes ['a'..'z']
"z"
*Main>letztes "String als Liste" -- hier wird ein String als Liste übergeben
"e"
In diesen Beispielen wurden rekursive Aufrufe verwendet. Für Details von Rekursionen wird es ein eigenes Kapitel geben.