\startproduct Tag8 \environment HaskellCourseEnv \startnotmode [complete] \setupheadnumber [Tag] [7] \stopnotmode \Tag [Tag8] {Beispiel: Tabellen formatieren} \startmode [never] [Hier stehen Dinge, die zwar f"ur das korrekte Laden in den Haskell-Interpreter notwendig sind, aber nicht im \TeX-Quellcode erscheinen sollen.] Wir definieren den Modulkopf: \startCode > module Tag8 where \stopCode Da die Funktion \type{formatTable} in \type{test1} erw"ahnt, aber nirgends definiert wird (es ist schlie"slich eine "Ubung am Ende), erzeugt das Laden des Moduls eine Fehlermeldung. Die folgende Haskell-Definition verhindert dies. Falls die eigene Definition von \type{formatTable} in diesem Modul stattfindet, dann sollte die Zeile entfernt werden: \startCode > formatTable = error "not yet defined" \stopCode \stopmode Am heutigen Tag geht es nicht in erster Linie darum, neue Konzepte einzuf"uhren, sondern wir wollen sehen, was wir mit dem bereits Erlernten schon erreichen k"onnen. Wir wollen Tabellen formatieren, etwa so: \startCode > test1 = formatTable [R,L,L] > [Row [Entry "Funktionsname" > ,Entry "Typ" > ,Entry "wann" > ] > ,Row [Entry "sum" > ,Entry "Num a => [a] -> a" > ,Entry "Tag 4" > ] > ,Row [Entry "null" > ,Entry "[a] -> Bool" > ,Entry "Tag 5" > ] > ,Row [Entry "foldr" > ,Entry "(a -> b -> b) -> b -> [a] -> b" > ,Entry "noch nicht" > ] > ] \stopCode mit der zugeh"origen Ausgabe \startHaskell Tag8> putStrLn test1 Funktionsname Typ wann? sum Num a => [a] -> a Tag 4 null [a] -> Bool Tag 5 foldr (a -> b -> b) -> b -> [a] -> b noch nicht \stopHaskell Die Funktion \type{formatTable} bekommt also eine Liste von Spaltenspezifikationen und eine abstrakte Beschreibung der Eintr"age der Tabelle und macht daraus eine sch"on formatierte Ausgabe, die die einzelnen Spalten gem"a"s der Spezifikation links- oder rechtsb"undig ausrichtet und die Spaltenbreiten so w"ahlt, da"s sie f"ur die l"angsten Eintr"age ausreichend platz bieten. Vorab etwas zur oben erw"ahnten Funktion \type{putStrLn}. Diese hat einen interessanten Typ: \startHaskell Tag8> :t putStrLn String -> IO () \stopHaskell Es handelt sich bei \type{putStrLn} um eine Ausgabefunktion. Das Argument ist ein \type{String}, das Resultat eine sogenannte \type{IO}-Aktion. Wir werden bald mehr "uber Ein- und Ausgabe lernen, f"ur den Moment gen"ugt es zu wissen, da"s man diese Funktion am interaktiven Prompt verwenden kann, um einen \type{String} {\em interpretiert} ausgeben zu lassen. Was das hei"st, l"a"st sich am besten an Beispielen demonstrieren. In Haskell kann man einige Steuerzeichen als Escape-Sequenzen schreiben, zum Beispiel einen Zeilenumbruch als \type{\n}, einen Tabulator als \type{\t} oder einen Backspace-Charakter als \type{\b}. \startHaskell Tag8> "ersteZeile\tund\nzweite Zeile\tEndw\be" "ersteZeile\tund\nzweite Zeile\tEndw\be" \stopHaskell Wie man sieht, werden diese Steuerzeichen von der normalen String-Ausgabefunktion uninterpretiert gelassen, man kann zwar genau sehen, welche Steuerzeichen wo enthalten sind, aber nicht, wie der Text wirklich auss"ahe. Es findet eben keine \quotation{echte} Ausgabe des Strings statt, sondern vielmehr eine Hilfsanzeige f"ur den Programmierer von Seiten des Interpreters. Eine Verwendung von \type{putStrLn} hingegen f"uhrt wirklich zur Ausgabe des Strings mitsamt Interpretation aller Steuerzeichen: \startHaskell Tag8> putStrLn "ersteZeile\tund\nzweite Zeile\tEndw\be" erste Zeile und zweite Zeile Ende \stopHaskell Da wir Tabellen ausrichten wollen, ist es nat"urlich hilfreich, so eine Funktion zur Hand zu haben, denn wir wollen die Ergebnisse ja auch in einer \quotation{sch"onen} Form begutachten k"onnen. Nun aber zum eigentlichen Thema. Wir zerlegen die Aufgabe in mehrere Einzelteile: \startitemize[packed] \item Wir definieren geeignete Datentypen. \item Wir schreiben eine Funktion, die einen String in einer gewissen Breite linksb"undig, rechtsb"undig oder zentriert ausrichtet. \item Wir schreiben eine Funktion, die die Spaltenbreiten berechnet, die notwendig sind, um die Tabelle erfolgreich auszurichten. \item Schlie"slich schreiben wir die Funktion, die die Tabelle ausrichtet. \stopitemize \Schritt {Datentypen definieren} Wir definieren zun"achst einige Datentypen, die f"ur unsere Applikation die Typsicherheit erh"ohen. Dadurch, da"s wir etwa Tabellenzeilen und -eintr"age mit gesonderten Typen versehen, erh"ohen wir die Lesbarkeit des Codes und auch etwaiger Typfehler f"ur uns. Wir beginnen mit einem Datentyp, der die drei M"oglichkeiten umfa"st, wie eine Tabellenspalte ausgerichtet werden kann: linksb"undig, zentriert und rechtsb"undig. \startCode > data Align = L | C | R \stopCode Der Datentyp \type{Align} hat also drei Konstruktoren, n"amlich \type{L}, \type{C} und \type{R}. All die Konstruktoren haben keine weiteren Argumente. Tabelleneintr"age sind im Prinzip Zeichenketten, aber wir markieren sie mit einem eigenen Konstruktor \type{Entry}, um sie von anderen Strings zu unterscheiden: \startCode > data Entry = Entry String \stopCode Der Datentyp \type{Entry} hat damit nur einen Konstruktor. Dieser hei"st ebenfalls \type{Entry} (diese Namensgleichheit ist in Haskell erlaubt und auch g"angige Praxis in solchen F"allen, in denen ein Typ nur einen Konstruktor besitzt). Dieser Konstruktor hat ein Argument vom Typ \type{String}. In "ahnlicher Weise definieren wir nun Tabellenzeilen. Tabellenzeilen sind Listen von Eintr"agen, daher definieren wir \startCode > data Row = Row [Entry] \stopCode Das gen"ugt vorerst als Vorbereitung. \Schritt {Einzelne Eintr"age ausrichten} Das Ziel dieses Abschnittes ist es, eine einzelne Zelle, deren Breite wir bereits kennen, auszurichten. Wir wollen eine Funktion \startCode > formatEntry :: Align -> Int -> Entry -> String \stopCode schreiben, die mit Hilfe einer Ausrichtung und einer Breitenangabe (der Typ \type{Int} ist ein Typ f"ur ganze Zahlen mit Gr"o"senbegrenzung; wir verwenden ihn dann, wenn wir keine extrem gro"sen Zahlen erwarten, weil er effizienter ist) aus einem Tabelleneintrag eine Zeichenkette eben dieser Breite erstellt, in der der Tabelleneintrag gem"a"s der gegebenen Ausrichtung formatiert ist. Beispiel: \startHaskell Tag8> formatEntry C 19 (Entry "Eintrag") " Eintrag " \stopHaskell Da wir die Breite sp"ater vorab berechnen werden, und zwar ausreichend anhand der gesamten Tabelleneintr"age f"ur eine Spalte, ist es nicht erforderlich, da"s \type{formatEntry} korrekt arbeitet, falls die gegebene Breite nicht gro"s genug f"ur den Eintrag ist. Offenbar m"ussen wir, um unser Ziel zu erreichen, den Eintrag mit einer gewissen Anzahl von Leerzeichen auff"ullen, wobei die Anzahl der Leerzeichen aus der L"ange des Eintrages und der gegebenen Breite zu errechnen ist. Die Funktion \type{length} kennen wir bereits zum Berechnen der L"ange einer Liste (und damit eines Strings). Hilfreich w"are es, wenn wir eine Funktion \startCode > spaces :: Int -> String \stopCode h"atten, die, gegeben eine Zahl $n$, eine Zeichenkette mit $n$ Leerzeichen liefert, etwa \startHaskell Tag8> spaces 5 " " \stopHaskell Das sollte mit unseren Kenntnissen kein Problem mehr sein: \startCode < spaces 0 = "" < spaces n = ' ' : spaces (n-1) \stopCode Wie so oft, verwenden wir Rekursion in der Definition der Funktion. Eine Folge von $0$ Leerzeichen entspricht der leeren Zeichenkette. Eine Folge von $n$ Leerzeichen entsteht daraus, da"s wir an $n-1$ Leerzeichen ein weiteres anh"angen, mittels Cons-Operator. Wir verwenden \quotation{pattern-matching} f"ur das erste Argument. Der erste Fall trifft zu, wenn wir \type{spaces} auf \type{0} anwenden. Der zweite Fall trifft folglich nur dann zu, wenn wir \type{spaces} auf einen \type{Int} ungleich \type{0} anwenden. Die Funktion \type{spaces} terminiert nicht, wenn wir sie auf eine negative Zahl anwenden. Wir werden in einer der folgenden Lektionen noch lernen, wie man in einem solchen Fall eine aussagekr"aftige Fehlermeldung produzieren kann. Tats"achlich bietet die Haskell-Prelude eine allgemeinere Funktion \type{replicate} mit dem Typ \type{Int -> a -> [a]}, welche aus einer Zahl $n$ und einem einzelnen Zeichen die Zeichenkette bildet, die $n$ Mal das betreffende Zeichen enth"alt. Wir k"onnen \type{spaces} daher alternativ wie folgt definieren \startCode > spaces n = replicate n ' ' \stopCode \startAufgabe Schreibe Deine eigene Version \type{replicate'} von \type{replicate}. \stopAufgabe Es ist nun nicht mehr schwierig, \type{formatEntry} zu definieren. Wir beginnen mit einem ersten Anlauf f"ur die zentrierte Formatierung: \startCode < formatEntry C width (Entry entry) = < spaces (div (width - length entry) 2) < ++ entry < ++ spaces (div (width - length entry + 1) 2) \stopCode Zun"achst verwenden wir \quotation{pattern matching} f"ur die Argumente: Das erste Muster ist \type{C}, das hei"st, der betreffende Fall, den wir soeben geschrieben haben, trifft nur dann zu, wenn das erste Argument auch \type{C} ist. Das zweite Muster ist einfach ein Name, hier passiert also nichts weiter, als da"s der \type{Int}-Parameter an den Namen \type{width} gebunden wird. Das dritte Argument ist vom Typ \type{Entry}. Eintr"age sind -- so wie wir sie definiert haben -- immer Zeichenketten, die mit dem Konstruktor \type{Entry} markiert werden. Durch das Muster \type{Entry entry} sorgen wir daf"ur, da"s wir die Zeichenkette wieder aus dem Eintrag extrahieren und da"s der Name \type{entry} an diese Zeichenkette gebunden wird. Das Resultat besteht aus der Konkatenation (unter Verwendung des bereits bekannten Operators \type{++}) von drei Zeichenketten. Die mittlere ist der Eintrag selbst, die beiden anderen sind Folgen von Leerzeichen, die mit der Funktion \type{spaces} erzeugt werden. Insgesamt m"ussen wir \type{width - length entry} Leerzeichen einf"ugen, um auf die Breite \type{width} zu kommen. Diese Anzahl teilen wir in etwa zwei gleich grosse Teile und f"ugen diese Teile vorne und hinten an den Eintrag an. F"ur die Teilung verwenden wir dabei den Operator \startCode < div :: Integral a => a -> a -> a \stopCode Dieser f"uhrt eine Ganzzahldivision durch (also mit Abrunden). Es gilt f"ur alle \type{n} vom Typ \type{Int}, da"s \startnarrower \startlines \type{div n 2 + div (n+1) 2 == n} \stoplines \stopnarrower Nat"urlich ist es unsch"on, da"s der Teilausdruck \type{width - length entry} in der Definition von \type{formatEntry} zweimal vorkommt. Das erh"oht nicht nur den Schreibaufwand -- es ist auch ineffizient, denn normalerweise wird ein Compiler diesen Ausdruck auch zweimal auswerten (der \GHC\ unterst"uzt eine Optimierung, die \quotation{common subexpression elimination} hei"st, aber der Aufwand f"ur die Erkennung solcher gemeinsamen Teilausdr"ucke ist sehr hoch, so da"s sie nur in sehr seltenen F"allen funktioniert). Besser ist es daher, den gemeinsamen Teilaudruck selbst zu identifizieren und ihm in einem \type{let}-Konstrukt einen tempor"aren Namen zu geben. Das \type{let}-Konstrukt ist f"ur uns neu und wird hier wie folgt benutzt: \startCode > formatEntry C width (Entry entry) = > let > { n = width - length entry } > in > spaces (div n 2) ++ entry ++ spaces (div (n+1) 2) \stopCode Zwischen den Schl"usselw"orten \type{let} und \type{in} k"onnen mehrere lokale Funktionsdefinitionen stehen, mit derselben Syntax, wie wir auch globale (also modulweite) Funktionen definieren. In diesem Fall definieren wir nur eine einzelne Konstante (also eine Funktion ohne Argumente), n"amlich \type{n}, die wir dann in dem Ausdruck, der auf das \type{in} folgt, benutzen d"urfen. \startAufgabe Definiere die beiden fehlenden F"alle von \type{formatEntry} f"ur das links- und rechtsb"undige Ausrichten eines einzelnen Eintrags. \stopAufgabe \Schritt {Spaltenbreiten berechnen} In diesem Abschnitt wollen wir eine Funktion \startCode < columnWidths :: [Row] -> [Int] \stopCode schreiben, die aus einer Liste mit Tabellenzeilen eine Liste mit Spaltenbreiten berechnet. Zun"achst ist festzuhalten, da"s die Ausrichtung auf die Spaltenbreiten keinen Einfl"u"s hat. Je nach Ausrichtung werden nur Leerzeichen an verschiedenen Stellen aufgef"ullt, allein der breiteste Eintrag pro Spalte bestimmt die notwendige Breite einer Spalte. Wir gehen der Einfachheit halber davon aus, da"s jede Zeile gleich viele Eintr"age enth"alt (etwa $n$ viele). In diesem Fall wird die Ergebnisliste also auch $n$ Spaltenbreiten enthalten. Da"s die Eintr"age der Tabelle in der Eingabe nach Zeilen gruppiert sind, ist f"ur unsere Aufgabe eher hinderlich. Daher wird ein erstes Teilziel sein, die Tabelle zu \quotation{transponieren}, also nach Spalten statt nach Zeilen zu gruppieren. Um dem p"adagogischen Anspruch gerecht zu werden, definieren wir uns daf"ur noch einen Datentyp: \startCode > data Column = Column [Entry] \stopCode Die Funktion, die die Transposition durchf"uhrt, hat dann folgenden Typ: \startCode > transposeTable :: [Row] -> [Column] \stopCode Auch hier verwenden wir wieder Rekursion, und wir beginnen mit zwei einfachen Basisf"allen: \startCode > transposeTable [] = [] > transposeTable [Row es] = map (\e -> Column [e]) es \stopCode Eine Tabelle ganz ohne Zeilen ist nat"urlich auch eine Tabelle ganz ohne Spalten (diesen Fall k"onnten wir auch ausschlie"sen). In der zweiten Zeile sehen wir ein sogenanntes \quotation{nested pattern}, was von der bisherigen Form eines Konstruktors, gefolgt von Variablennamen, abweicht. Das Muster trifft genau dann zu, wenn die Liste von Zeilen genau ein Element enth"alt. Dieses Element (vom Typ \type{Row}) mu"s mit dem Konstruktor \type{Row} gebildet worden sein (was immer der Fall ist), und das Feld des Konstruktors (vom Typ \type{[Entry]}) wird an den Namen \type{es} gebunden. Eine Tabelle mit genau einer Zeile l"a"st sich transponieren, indem wir f"ur jeden Eintrag eine Spalte erstellen, die genau einen Eintrag enth"alt. Dazu machen wir Gebrauch von \type{map}. Zur Erinnerung: Die Funktion \type{map} nimmt eine Funktion und eine Liste und wendet die Funktion auf jedes Element der Liste an. In unserem Fall haben wir eine Liste von Eintr"agen (den Eintr"agen unserer einen Zeile in der Tabelle), und die Funktion, die angewendet werden soll, ist durch einen Lambda-Ausdruck gegeben: Wir nehmen einen (also jeden) Eintrag \type{e} und bilden ihn ab auf eine Spalte, die genau diesen Eintrag enth"alt. Fertig! Der noch ausstehende allgemeine Fall ist das komplizierteste St"uckchen Code in der gesamten Lektion, aber wir werden das Schritt f"ur Schritt erkl"aren. Hier zun"achst die Definition: \startCode > transposeTable (Row es : rows) = > let > { rec :: [Column] > ; rec = transposeTable rows > ; addToColumn :: Entry -> Column -> Column > ; addToColumn e (Column es) = Column (e : es) > } > in > zipWith addToColumn es rec \stopCode Auch hier wieder ein \quotation{nested pattern}. Das Muster trifft zu, wenn die Liste mittels Cons-Operator gebildet wurde (also mindestens ein Element enth"alt). Tats"achlich wird die Liste immer mindestens zwei Elemente enthalten, weil im Fall der einelementigen Liste bereits der oben definierte Basisfall zutrifft. Der Kopf der Liste mu"s von der Form \type{Row es} sein, der Rest der Liste wird an \type{rows} gebunden. Wir begegnen dem \type{let}-Konstrukt erneut. Auch hier w"are es -- wie bei der ersten Verwendung -- m"oglich, ohne \type{let} auszukommen. Die definierten Werte k"onnten im Ausdruck nach dem \type{in} einfach durch ihre Definitionen ersetzt werden (bei der Funktion \type{addToColumn}) mit Hilfe eines Lambda-Ausdrucks. Die Einf"uhrung von tempor"aren Namen dient hier der Zerlegung des Ausdrucks in kleinere, handlichere Bestandteile, denen wir zu Dokumentationszwecken auch nochmals Typsignaturen verpassen (das ist, wie (fast) immer, nicht n"otig; w"urden die Typsignaturen fehlen, dann w"urden sie automatisch vom Compiler inferiert). Die Idee besteht darin, erst alle bis auf die erste Zeile durch einen rekursiven Aufruf der Funktion \type{transposeTable} zu transponieren. Da die Restliste noch mindestens eine Zeile enth"alt, ist das Resultat \type{rec} eine nicht-leere Liste von Spalten. Den Spalten fehlen jedoch ihre jeweils ersten Eintr"age, denn diese sind in der ersten Zeile (deren Eintr"age in \type{es} zwischengespeichert sind) definiert! Das Hinzuf"ugen eines ersten Eintrages zu einer Spalte leistet die Funktion \type{addToColumn} durch Verwendung des Cons-Operators. Wir haben nun zwei Listen: eine enth"alt die Eintr"age der ersten Zeile, die andere enth"alt die Spalten, denen die ersten Eintr"age fehlen. Beide Listen haben gleich viele Elemente, und das Resultat, an dem wir interessiert sind, entsteht dadurch, da"s beide Listen in eine Liste zusammengef"uhrt werden, und zwar, in dem die jeweils zueinandergeh"orenden Elemente der beiden Liste mit Hilfe der Funktion \type{addToColumn} kombiniert werden. Das genau leistest die Funktion \type{zipWith}, die in der Haskell-Prelude etwa wie folgt definiert ist: \startCode < zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] < zipWith combine [] ys = [] < zipWith combine xs [] = [] < zipWith combine (x:xs) (y:ys) = combine x y : zipWith combine xs ys \stopCode Die ersten beiden F"alle sorgen daf"ur, da"s beim Zusammenf"ugen zweier Listen unterschiedlicher L"ange die l"angere Liste abgeschnitten wird. Sobald eine der beiden Listen leer ist, ist das Resultat die leere Liste. Wenn beide Listen noch mindestens ein Element enthalten, dann trifft die dritte Zeile zu. In diesem Fall werden die Kopfelemente der beiden Liste mit der Funktion \type{combine}, dem ersten Argument der Funktion \type{zipWith} kombiniert und vorne an die rekursiv gebildete Restliste angeh"angt. Die maximale L"ange eines Spalteneintrags ist nun leicht gefunden: \startCode > maximumColumn :: Column -> Int > maximumColumn (Column es) = > let > { lengths :: [Int] > ; lengths = map (\(Entry e) -> length e) es > } > in > maximum lengths \stopCode Zun"achst bestimmen wir die L"angen der einzelnen Eintr"age mit Hilfe von \type{map}. Dann benutzen wir die bereits fr"uher erw"ahnte Funktion \type{maximum}, um das Maximum einer Liste zu bestimmen. Damit sind wir f"ur \type{columnWidths} ausreichend mit Hilfsmitteln best"uckt: \startCode > columnWidths :: [Row] -> [Int] > columnWidths rows = map maximumColumn (transposeTable rows) \stopCode Die Arbeitsweise dieser Funktion sollte mittlerweile ohne weitere Ekl"arung verst"andlich sein. \Schritt {Tabellen formatieren} Nun ist alle Vorarbeit geleistet, um die eigentliche Formatierung vornehmen zu k"onnen. Wir schreiben zun"achst noch eine Funktion \startCode > formatRow :: [Align] -> [Int] -> Row -> String \stopCode die eine einzelne Zeile formatiert. Hier haben wir ein "ahnliches Problem wie zuvor bei der Definition von \type{transposeTable}: Eine Zeile enth"alt f"ur jede Spalte einen Eintrag. Zus"atzlich haben wir f"ur jede Spalte eine Ausrichtug und eine Breite. Wir haben also insgesamt drei Listen derselben L"ange. Zudem haben wir bereits eine Funktion, n"amlich \type{formatEntry}, die sich eignet, jeweils eine Ausrichtung, eine Breite und einen Eintrag in eine Zeichenkette zu transformieren. Vorhin hatten wir zwei Listen mit Hilfe von \type{zipWith} zu einer Liste zusammengef"ugt. F"ur drei Listen gibt es die verwandte Funktion \type{zipWith3}, die ebenfalls in der Prelude definiert ist. Daher: \startCode > formatRow aligns widths (Row es) = > mergeStrings (zipWith3 formatEntry aligns widths es) \stopCode Der Aufruf von \type{zipWith3} liefert uns eine Liste von Strings, die die einzelnen, ausgerichteten Tabelleneintr"age f"ur eine Zeile enthalten. Diese m"ussen nun zu einem einzelnen String zusammengef"ugt werden. Die einfachste M"oglichkeit \startCode > mergeStrings :: [String] -> String > mergeStrings = concat \stopCode ist suboptimal, da auf diese Weise die Spalten ohne Zwischenraum aneinandergeh"angt werden. \startAufgabe Schreibe die Funktion \type{mergeStrings} so, da"s zwischen je zwei Spalten noch zwei Leerzeichen eingef"ugt werden. Beispiel: \startHaskell Tag8> mergeStrings ["Haskell","B.","Curry"] "Haskell B. Curry" \stopHaskell \stopAufgabe \startAufgabe Schreibe die Funktion \type{formatTable} mit dem Typ \type{[Align] -> [Row] -> String}. Verwende dabei die Funktion \startCode < unlines :: [String] -> String \stopCode die in der Prelude definiert ist und dazu dient, aus einer Liste von Strings, die jeweils eine Zeile enthalten, einen zusammenh"angenden String zu bauen, der Zeilenumbr"uche an den entsprechenden Stellen enth"alt. Teste die Funktion unter Verwendung von \type{putStrLn} und \type{test1}. Schreibe einen weiteren Test. \stopAufgabe \startLernziele \item Um lokale Funktionen oder wiederkehrende lokale Ausdr"ucke zu definieren, ist das \type{let}-Konstrukt hilfreich. \item Auch gr"o"sere Problemstellungen lassen sich bequem in kleine Bruchst"ucke zerlegen, die jeweils durch einzelne Funktionen realisiert werden k"onnen. \item Die Prelude definiert eine gro"se Anzahl hilfreicher Funktionen (etwa \type{map} oder \type{zipWith}), die man im t"aglichen Gebrauch oft ben"otigt. \stopLernziele \stoptext \stopproduct