Beispiel 3 - Datenbank
Übersicht: Beispiel 3 - Datenbank
Einleitung
In diesem Beispiel sollen Listen zu Datenbankzwecken eingesetzt werden, aus zwei Quelllisten soll eine Ausgabeliste berechnet werden. Hierfür werden Listen von Tupeln verwendet - eine Abweichung vom relationalen Datenbankmodell (Mengen von Tupeln). Die Reihenfolgen-Eigenschaft von Listen wird dabei ausgenutzt werden.
Ausgangslage sollen zwei Listen einer Ausbildungsklasse sein. Die 1. Liste beinhaltet binäre Tupel aus Namen und einer dazugehörigen eindeutigen Identifikationsnummer (analog dem Primärschlüssel einer relationalen Datenbank), sie ist nach den Namen sortiert. Die 2. Liste beinhaltet binäre Tupel aus Identifikationsnummer (korrespondierend zu den Identifikationsnummern der 1. Liste) und Prüfungsergebnis, sie ist nach der Identifikationsnummer sortiert. Ziel soll es sein, eine Liste zu berechnen, die Tupel aus Namen, Prüfungsergebnis und Rangfolge des Prüfungsergebnis beinhaltet und ebenfalls sortiert ist nach dem Namen.
Das Beispiel wird top-down entwickelt, zuerst werden die allgemeinsten Schritte der Problemlösung aufgeführt (ohne die Definitionen der dort verwendeten Funktionen bereits einzuführen). Die verarbeiteten Daten in dieser Anwendung sind die Namen, Nummern und Noten von Klassenmitgliedern sowie die entstehenden Ränge. Zur besseren Lesbarkeit werden hierfür Typsynonyme eingeführt. Zur Vereinfachung definieren wir die oben beschriebenen und in der Anwendung verarbeiteten Tupellisten für Namen - Nummern, Nummern - Noten und das Endergebnis Namen - Noten - Ränge:
01 type Name = String
02 type Iden = Int
03 type Mark = Int
04 type Rank = Int
05 -- Tabellen
06 type Codes = [(Name,Iden)]
07 type Marks = [(Iden,Mark)]
08 type Ranks = [(Name,Mark,Rank)]
09
10 classlist :: (Codes,Marks) -> Ranks
11 classlist = rank . collate
12
13 display :: Ranks -> String
|
3-1.txt |
Codebeispiel 25
classlist ist das eigentliche "Programm" und berechnet aus den Eingabelisten die Ergebnisliste aus Namen, Noten und Rängen. display dient der formatierten Darstellung der Ergebnistupelliste. classlist läßt sich intuitiv in zwei Teilschritte zerlegen, die Assoziation von Namen mit Noten (durch Auswertung und Eliminierung der Identifikationsnummern, analog zu einem Datenbank-Join) und das anschließende Hinzufügen von Rängen. Die entsprechenden Schritte werden durch die Funktionen collate und rank erzielt.
Join der Ausgangstabellen (collate)
01 -- Zwei Tabellen zu einer Namen-Noten-Tabelle zusammenführen
02 collate :: (Codes, Marks) -> [(Name,Mark)]
03 collate = sortby name . remove . zipp . cross (sortby iden,id)
04 where name (xn,xm) = xn
05 iden (xn,xi) = xi
06
07 -- Zwei Tupel zu einem verbinden und das 2. Element des 2. Tupels entfernen
08 remove :: [((a,b),(b,c))] -> [(a,b)]
09 remove = map (cross (fst,snd))
|
3-2.txt |
Codebeispiel 26
Die cross-Funktion wendet die (2) Funktionen eines Tupels auf die korrespondierenden Elemente eines Datentupels an und liefert die Ergebnisse als Tupel. Im ersten Schritt sortiert collate mittels der cross-Funktion die Codes-Liste, die zu Beginn nach Namen sortiert ist, nach Identifikationsnummern. Die zweite Liste des Eingabetupels, Marks, ist bereits nach der Identifikationsnummer sortiert und wird in diesem Schritt nicht transformiert (Anwendung der Identitätsfunktion id). Das Ergebnis des ersten Schrittes sind zwei nach Identifikationsnummern sortierte Listen gleicher Länge, bei denen für alle Indices die Elemente korrespondieren. Im zweiten Schritt wird mittels der zipp-Funktion aus dem Listen-Tupel eine Tupel-Liste (deren Tupel jeweils die vier Elemente der Eingabelisten organisiert in zwei Untertupeln beinhalten: ((Name,Iden),(Iden,Mark)). Die remove-Funktion im dritten Schritt entfernt die Identifikationsnummer aus den beiden Untertuppeln, wickelt dabei quasi die gewünschten Elemente aus den Untertupeln aus und bildet daraus eine Liste von Tupeln der Form (Name,Mark). Diese wird abschließend nach dem Namen sortiert und das Ergebnis der Funktion steht damit fest.
Berechnen der Ränge (rank)
Die aus collate gewonnene Liste muß mit Hilfe der rank-Funktion noch um die Rang-Information angereichert werden. Dazu wird allgemein auf jedes Tupel (Name,Mark) die Funktion score angewendet. Die score-Funktion bestimmt den Rank, in dem sie die Länge der Liste der Tupel, die größere Noten als das aktuelle Tupel aufweisen, berechnet und um 1 erhöht. Diese Liste wird durch Filtern der Gesamtliste mit der beats-Funktion bestimmt, die einen einfachen Vergleich ausführt. Tupel gleicher Punktzahl erhalten bei diesem Prinzip den gleichen Rang (da ja jeweils die gleiche Anzahl Tupel größere Punktzahl aufweist), werden jedoch für punktschwächere Tupel zusammengezählt (da sie ja alle größere Werte als diese aufweisen).
01 rank :: [(Name,Mark)] -> Ranks
02 rank xs = map (score xs) xs
03
04 -- Rang eines bestimmten Tupels berechnen, dazu Filtern der Liste auf alle Elemente, die das aktuelle Tupel "schlagen"
05 score :: (Name,Mark) -> (Name,Mark,Rank)
06 score xs (xn,xm) = (xn,xm,1 + length (filter (beats xm) xs))
07
08 -- Prädikat, ob ein Tupel eine bestimmte Note übertrifft
09 beats xm (yn,ym) = xm < ym
|
3-3.txt |
Codebeispiel 27
Eine effizientere Variante der Rangzuordnung arbeitet folgendermaßen: Zuerst werden die Ausgangstupel nach den Noten abwärts sortiert (reverse), dann werden Ränge zugeordnet und schließlich wird wieder nach dem Namen sortiert. Die Rangzuordnung mit assign ordnet zunächst jedem Element den Rang entsprechend dem Index seiner Listenposition zu (initialise). Nachfolgend müssen die Fälle gleicher Punktzahl berücksichtigt werden: Werden Elemente gleicher Note gefunden, erhalten sie solange den letzten korrekten Rang, bis reduce ein Element geringerer Note findet (dieses behält seinen vorberechneten Rang). Der Algorithmus wird mit scan in jede Teilliste der umsortierten Ausgangsliste gefaltet, d.h, für eine neue Liste wird zu jedem Index die Faltung bis zum korrespondierenden Listenelement laufen.
01 -- Ränge berechnen mittels Durchnumerieren und Herausstreichen zu niedriger Ränge
02 rank = sortby name . assign . reverse . sortby mark
03 where mark (xn,xm) = xm
04 name (xn,xm,xr) = xn
05
06 -- Ränge zuweisen
07 assign :: [(Name,Mark)] -> Ranks
08 assign xs = scanl1 reduce . initialise
09
10 -- Ränge der Reihe nach initialisieren
11 initialise :: [(Name,Mark)] -> Ranks
12 initialise = zipWith mktriple xs [1..]
13 where mktriple ((xn,xm),xr) = (xn,xm,xr)
14
15 -- zu niedrige Ränge hochsetzen
16 reduce (xn,xm,xr) (yn,ym,yr) = if ym == xm then (yn,ym,xr) else (yn,ym,yr)
|
3-4.txt |
Codebeispiel 28
Sortieren mit sortby
Für das collate ist offensichtlich noch eine Sortierfunktion zu definieren. Dies machen wir mit sortby, einer Funktion, die neben einer Liste des Typs a eine Funktion als Parameter aufnimmt, die die Elemente a der Liste in die zu vergleichenden Elemente des Typs b transformiert. Das Ergebnis von sortby ist wieder eine Liste des Typs a, nämlich die Ursprungsliste in sortierter Reihenfolge.
01 -- Sortieren einer beliebigen Liste mit einer Funktion, die Listenelemente in geordnete Werte überführt. Sortierung durch Einfalten einer Funktion, die die Ergebnisliste mitführt und das nächste Element sortiert einfügt
02 sortby :: Ord b => (a -> b) -> [a] -> [a]
03 sortby f = foldr (insertby f) []
|
3-5.txt |
Codebeispiel 29
Das Prinzip ist denkbar einfach, die Funktion insertby f wird zwischen die Listenelemente gefaltet und mit der leeren Liste und dem letzten Listenelement gestartet. insertby nimmt eine Liste auf und fügt ein weiteres Element sortiert ein. Die Ergebnisliste ist Grundlage des nächsten Einfügevorgangs durch insertby. insertby selbst nutzt span zusammen mit dem Testprädikat f, um die bisherige Liste in ein Tupel aus kleineren und größeren Elementen als das einzufügende Element zu zerlegen und insert, um das Element x mit diesen beiden Teillisten zu konkatenieren (dazwischen einzufügen).
01 -- Sortiertes Einfügen in eine Liste mit Hilfe eines Vergleichsprädikates
02 insertby :: (Ord b) => (a -> b) -> a -> [a] -> [a]
03 insertby f x = insert . span test
04 where insert (xs,ys) = xs ++ [x] ++ ys
05 test y = (f y < f x)
06
07 -- Aufteilen einer Liste in ein Tupel der Teillisten, Trennstelle ist das erste Erfüllen eines Prädikates
08 span :: (a -> Bool) -> [a] -> ([a],[a])
09 span = (takeWhile p xs, dropWhile p xs)
|
3-6.txt |
Codebeispiel 30
Wie bei rank gibt es auch für sortby eine effizientere Variante. Der oben beschriebene Ansatz entspricht dem Direct Insertion Sort-Algorithmus, der ein quadratisches Laufzeitverhalten aufweist. Nachfolgend definieren wir sortby mit dem Mergesort-Algorithmus mit (n log n)-Laufzeitverhalten. Mergesort nutzt zwei Ideen:
- Zwei gegebene sortierte Listen können durch Mischen zu einer einzigen sortierten Liste zusammengefaßt werden. Dazu wird stets das Minimum der beiden Listenköpfe bestimmt, das auch dem Minimum aller Elemente der beiden Listen entspricht. Dieses Minimum wird der entsprechenden Liste entnommen und der Ergebnisliste hinzugefügt. Das Verfahren endet, sobald eine der beiden Ausgangslisten leer ist - der Rest der anderen Liste kann nun einfach an die Ergebnisliste angehängt werden, da zwangsläufig alle Elemente größer als die bisherigen Ergebniselemente sind.
- Die Sortierung einer Liste kann dank des Mischens auf die Sortierung von zwei Teillisten zurückgeführt werden. Die beiden Teillisten sollen sich in der Länge höchstens um 0 oder 1 unterscheiden. Die Teillisten sind kürzer als die Ursprungslisten und somit ist ihre Sortierung ein einfacheres Problem. Wird diese Aufteilung wiederholt, so enthalten die Teillisten irgendwann nur noch 1 oder gar kein Element - sie sind damit sortiert. Ab diesem Punkt kann durch Mischen die fertig sortierte Liste hergestellt werden.
01 sortby f [] = []
02 sortby f [x] = [x]
03 sortby f (x : y : xs) = mergeby f (cross (sortby f, sortby f) (divide (x : y : xs)))
04
05 -- Eine Liste in zwei Teillisten zerlegen (abwechselnd auf zwei Listen verteilen, bis die leere Liste erreicht ist)
06 divide :: [a] -> ([a],[a])
07 divide = foldr allocate ([],[])
08 where allocate x (ys,zs) = (zs,x:ys)
09
10 -- Zwei Listen mischen, bis eine Liste leer ist
11 mergeby :: Ord b => (a -> b) -> ([a],[a]) -> [a]
12 mergeby f ([],ys) = ys
13 mergeby f (x:xs,[]) = x:xs
14 mergeby f (x:xs,y:ys)
15 | f x <= f y = x : mergeby f (xs,y:ys)
16 | otherwise = y : mergeby f (x:xs,ys)
|
3-7.txt |
Codebeispiel 31
sortby führt in diesem Fall die Sortierung wie beschrieben auf
- 1. das Aufteilen der Liste in zwei Teillisten (divide)
- 2. das Sortieren der beiden Teillisten (cross (sortby f, sortby f))
- 3. das Mischen der sortierten Teillisten zur fertig sortierten Ergebnisliste
zurück. sortby bricht den rekursiven Abstieg bei Erreichen einer leeren Liste oder einer Liste mit einem Element (da diese Listen bereits sortiert sind) ab. divide erreicht die Aufteilung einer Liste in zwei Listen durch Falten mit der allocate-Funktion, die bei einem Tupel mit zwei leeren Listen anfängt (diese entsprechen den beiden Ergebnislisten), mit jedem Faltungsschritt die beiden Listen vertauscht und stets der rechten Liste das nächste Element der Ausgangsliste vorstellt. Im Ergebnis unterscheiden sich die Teillisten in der Länge um 0 oder 1. mergeby liefert als Ergebnis der Mischung im Falle einer leeren Liste die jeweils andere Liste (da hier nichts mehr gemischt werden muß), ansonsten nimmt es den jeweils kleineren Kopf der beiden Listen und stellt ihn einem rekursiven Aufruf von mergeby mit den Restlisten vor.
classlist definieren
Nun kann die oben bereits mit ihrer Typsignatur eingeführte classlist-Funktion definiert werden. Nach dem Einsetzen der collate- und rank-Definitionen ist noch eine Sortierung zu erkennen (sortby name), die durch eine nachfolgende Sortierung redundant ist (sortby mark), diese wird entfernt.
01 classlist = rank . collate
02 classlist = sortby name . assign . reverse . sortby mark . sortby name . zipp . cross (map fst . sortby iden, map snd)
03 classlist = sortby name . assign . reverse . sortby mark . zipp . cross (map fst . sortby iden, map snd)
|
3-8.txt |
Codebeispiel 32
Bildschirmausgabe der Ergebnistabelle
Zur Anzeige der Ergebnisliste wird noch die bereits erwähnte display-Funktion benötigt, die aus einer Liste von (Name,Note,Rang) - Tupeln einen String erzeugt. Dazu wird die line-Funktion zur Konvertierung der einzelnen Tupel auf die Liste gemappt (Ergebnis ist eine Liste von Strings), dieser Liste von Strings wird mit der heading-Funktion ein Kopfzeilenstring vorangestellt und schließlich wird die Stringliste mit der unlines-Funktion zu einer einzigen Liste (also einem String) konvertiert, wobei zwischen die einstigen Teilstrings Zeilensprünge \n gefaltet werden.
01 -- Umwandeln der Ergebnistupel in einen String durch 1. Umwandeln aller Tupel, 2. Versehen mit Kopfzeile und 3. Konkatenieren der Strings mit "\n"
02 display :: [(Name,Mark,Rank)] -> String
03 display = unlines . (heading :) . map line
04
05 -- Prelude-Funktion, Konkatenieren einer Liste von Strings zu einem String über "\n"
06 unlines :: [String] -> String
07 unlines = foldr join where join xs ys = xs ++ "\n" ++ ys
|
3-9.txt |
Codebeispiel 33
Die line- und heading-Funktionen realisieren die Formatierung der einzelnen Zeilen. Die Namens-Spalte wird dabei linksbündig mit 12 Zeichen Breite, die Notenspalte rechtsbündig mit 4 Zeichen Breite und die Rangspalte rechtsbündig mit 6 Zeichen Breite dargestellt. Das Prinzip der entsprechenden Funktionen ljustify und rjustify ist einfach, es wird je nach Bündigkeit die Differenz zwischen Zielbereite und tatsächlicher Elementbreite an Leerzeichen vorangestellt bzw. angehängt (die spaces-Funktion erzeugt dabei einen Leerzeichenstring der gewünschten Länge).
01 -- Kopfzeile
02 heading :: String
03 heading = ljustify 12 "Name" ++ rjustify 4 "Mark" ++ rjustify 6 "Rank"
04
05 -- Ein Ergebnistupel in einen String umwandeln (Name linksbündig 12 Zeichen, Note 4 Zeichen rechtsbündig, Rang 6 Zeichen rechtsbündig
06 line :: (Name,Mark,Rank) -> String
07 line (xn,xm,xr) = ljustify 12 xn ++ rjustify 4 (show xm) ++ rjustify 6 (show xr)
08
09 -- rechts- bzw. linksbündiges Ausrichten von Strings
10 ljustify, rjustify :: Int -> String -> String
11 ljustify n xs = xs ++ spaces (n - length xs)
12 rjustify n xs = spaces (n - length xs) ++ xs
13 spaces x = replicate x ´ ´
|
3-10.txt |
Codebeispiel 34
Code generated with AusarbeitungGenerator Version 1.1, weblink