programmierung.jpg

 

In diesem Teil erkläre ich dir, wie Listen in Haskell umgesetzt werden, wie du rekursiv auf Listen zugreifst und mit ihnen arbeitest.  

 

Listen sind eines der wichtigsten Werkzeuge in Haskell, um mit ihnen zu arbeiten, musst du verstehen, wie Listen in Haskell aufgebaut sind. Eine Liste ist eine geordnete Menge von Elementen gleichen Typs.  Auch wenn die Arbeit mit Listen am Anfang sehr gewöhnungsbedürftig ist, hat man erstmal den grundlegenden Aufbau von Listen in Haskell verstanden, kann man sehr einfach mit Ihnen arbeiten und auch komplexe Probleme mit Listen lösen. Seine wahre Stärke in Bezug auf Listen spielt Haskell mit seinen sogenannten Listcomprehensions aus, auf die ich in einem separaten Blogbeitrag eingehen werde.

 

 

Listen in Haskell anlegen

Listen lassen sich in Haskell auf verschiedene Art und Weise anlegen.

 

[1, 2, 3, 4, 5]

ist eine Liste, die die Zahlen 1 bis 5 enthält.

Wir können dieser Liste auch eine Variable zuweisen:

zahlen = [1, 2, 3, 4, 5]

 

Listen können in Haskell auch leer sein, das heißt keine Elemente enthalten, dazu schreiben wir einfach nichts zwischen die eckigen Klammern:

leereListe = []

 

Jeder String ist eine Liste von Zeichen. Somit ist ['h', 'a', 'l', 'l', 'o'] das Gleiche wie "hallo".

 

Du kannst in Haskell auch eine Liste von Listen definieren, solange die Listen vom gleichen Typ sind:

[[1, 2], [5, -2], []]

 

 

Zerlegung in Kopf und Rest

In Haskell sind Listen so definiert, dass es den Listenkopf und den Rest gibt. Der Kopf, also das erste Element der Liste, ist das einzige Element, auf dass man zugreifen kann. Natürlich werden wir gleich sehen, dass man auch auf jedes andere Element zugreifen kann, aber nur unter Einhaltung dieser Regel. 

Um auf den Kopf einer Liste zuzugreifen, stellt Haskell dir den : Operator zur Verfügung.
Die Liste [1, 2, 3, 4, 5] lässt sich auch 1 : [2, 3, 4, 5] schreiben. 

Im weiteren Verlauf dieses Beitrages wirst du oft (x:xs) als Bezeichnung für eine Liste finden. Diese Bezeichnung spiegelt genau die Aufteilung in Kopf und Rest einer Liste wider, so können wir mit x auf den Kopf einer Liste zugreifen und mit xs auf den Rest der Liste. Also ist xs die Ursprungsliste ohne das erste Element (Kopf).

Dazu ein kleines Beispiel:

Nehmen wir an, wir haben folgende Liste erstellt: 

[1, 2, 3, 4, 5]

Diese Liste Bezeichnen wir in unserer Haskell Funktion mit (x:xs), das heißt 

x = 1

xs = [2, 3, 4, 5]

Wichtig ist, dass x ein einzelnes Element aus der Liste ist und xs wieder eine Liste ist.

 

Funktionen auf Listen

Um die Funktionsweise von Listen besser zu verstehen, werden wir uns ein paar Beispiele anschauen. Wir wollen im Folgenden verschiedene Funktionen für Listen implementieren. 

 

Prüfen, ob eine Liste leer ist

Als Erstes wollen wir eine Funktion istLeer schreiben, die prüft, ob eine gegebene Liste leer ist und uns den entsprechenden Wahrheitswert zurückliefert. 

istLeer :: [a] -> Bool
istLeer [] = True
istLeer (x:xs) = False

Diese Funktion nutzt das Pattern-Matching von Haskell. Sagen wir, wir übergeben der Funktion eine Liste mit dem Namen "list", jetzt prüft Haskell, ob list = [], das ist natürlich immer der Fall, wenn die übergebene Liste leer ist. Sollte das nicht der Fall sein, lässt sich list auch in der Form (x:xs) schreiben. Dabei ist x das erste Element der Liste (also der Kopf oder Head) und xs der Rest der Liste. Auch eine Liste, die nur ein Element enthält, lässt sich so schreiben. Zum Beispiel kannst du die Liste [1] auch in der Form 1 : [] schreiben.

 

Ein Element an das Ende der Liste anhängen

Wir wollen eine Funktion snoc schreiben, die ein einzelnes Element an das Ende einer Liste anhängt. 

snoc :: a -> [a] -> [a]
snoc a [] = [a]
snoc a (x:xs) = x : (snoc a xs)
 

Die Funktion snoc bekommt ein Element und eine Liste übergeben und liefert als Ausgabe wieder eine Liste. Wenn die übergebene Liste leer ist, wird einfach eine Liste erstellt, die nur das übergebene Element enthält. Für den Fall, dass die Liste nicht leer ist, wird die Funktion rekursiv so lange aufgerufen, bis der definierte Abbruchfall eintritt. Da wir hier mit endlichen Listen arbeiten tritt dieser auf jeden Fall ein. 

 

Die Länge einer Liste ausgeben

Wir definieren eine Funktion laenge, die uns die Länge einer Liste liefert, also wie viele Elemente in einer Liste sind.

laenge :: [a] -> Int
laenge [] = 0
laenge (x:xs) = 1 + (laenge xs)

 

Erstes Element einer Liste ausgeben

erstesElement :: [a] -> a
erstesElement (x:xs) = x

 

Den Rest einer Liste ausgeben

Wir wollen eine Funktion rest schreiben, die uns eine Liste nach Entfernen des ersten Elements ausgibt. Ist die übergebene Liste leer, geben wir eine Fehlermeldung aus.

rest :: [a] -> [a]
rest [] = error "Leere Liste!"
rest (x:xs) = xs

 

Letztes Element einer List ausgeben

Wir schreiben eine Funktion letztesElement, die uns das letzte Element einer Liste zurückgibt. Bei einer leeren Liste geben wir eine Fehlermeldung aus.

letztesElement :: [a] -> a
letztesElement [] = error "Leere Liste!"
letztesElement (x:[]) = x
letztesElement (x:xs) = letztesElement xs

 

Letztes Element einer Liste entfernen

Wir wollen zu einer gegebenen Liste eine neue Liste erstellen, die alle Elemente bis auf das letzte Element enthält. Bei einer leeren Liste geben wir eine Fehlermeldung aus.

anfang :: [a] -> [a]
anfang [] = error "Leere Liste!"
anfang (x:[]) = []
anfang (x:xs) = x : anfang xs

 

Die ersten n Elemente einer Liste wiedergeben

Wir schreiben eine Funktion nimm, die die ersten n Elemente einer übergebenen Liste zurückgibt. Sind weniger als n Elemente in der Liste, werden so viele wie möglich zurückgegeben. 

nimm :: [a] -> Int -> [a]
nimm [] _ = []
nimm _ 0 = []
nimm (x:xs) n = x : nimm xs (n - 1)

 

Aus einer Liste n Elemente löschen

Wir schreiben eine Funktion verwerfe, die n Elemente aus einer Liste löscht. Enthält die Liste weniger als n Elemente, wird eine leere Liste zurückgegeben.

verwerfe :: [a] -> Int -> [a]
verwerfe [] _ = []
verwerfe liste 0 = liste
verwerfe (x:xs) n = verwerfe xs (n - 1)

 

Summe der Elemente einer Liste bilden

Wir schreiben eine Funktion summe, die die Summe aller Elemente der übergebenen, numerischen Liste bildet.

summe :: (Num a) => [a] -> a
summe [] = 0
summe (x:xs) = x + summe xs

 

Werte einer Liste verdoppeln

Wir wollen alle Werte einer numerischen Liste verdoppeln. 

verdopple :: (Num a) => [a] -> [a]
verdopple [] = []
verdopple (x:xs) = (x * 2) : verdopple xs

 

Verkettung von zwei Listen

Wir wollen zwei übergebene Listen gleichen Typs zu einer verketten.

verkette :: [a] -> [a] -> [a]
verkette [] liste = liste
verkette (x:xs) liste = x : verkette xs liste

 

Liste in umgekehrter Reihenfolge ausgeben

Wir wollen aus einer gegebenen Liste eine neue Liste erstellen, die die Elemente in umgekehrter Reihenfolge enthält.

rueckwaerts :: [a] -> [a]
rueckwaerts [] = []
rueckwaerts (x:xs) = snoc x (rueckwaerts xs) 

Die umgekehrte Reihenfolge bei einer leeren Liste ist natürlich auch wieder eine leere Liste. Sollte die übergebene Liste nicht leer sein, verkleinern wir sie so lange, bis sie leer ist und hängen jedes Mal den Kopf an das Ende der Liste.

 

Eine Liste aufteilen

Wir wollen eine Funktion aufteilen schreiben, die eine Liste an Position n aufteilt. 

aufteilen :: Int -> [a] -> ([a],[a])
aufteilen 0 list = ([], list)
aufteilen n [] = ([], [])
aufteilen n (h:t) = 
    let (tA, tB) = aufteilen (n-1) t
    in (h:tA, tB)


Konversation wird geladen