\startproduct Tag7 \environment HaskellCourseEnv \startnotmode [complete] \setupheadnumber [Tag] [6] \stopnotmode \Tag [Tag7] {\quotation{Pattern Matching} und eigene Datentypen} Heute werden wir eine Technik kennenlernen, die daf"ur sorgt, da"s wir sehr viel "ubersichtlichere und k"urzere Programme schreiben k"onnen. Als "Uberleitung auf diese Technik, die den Namen \quotation{pattern matching} tr"agt, blicken wir zun"achst einmal ein wenig voraus und schauen uns an, wie man in Haskell eigene Datentypen definieren kann. Auch diesmal wieder bildet der Quellcode zur Lektion ein eigenes Modul: \startCode > module Tag7 where \stopCode Wir beginnen, wie so oft, mit einem Beispiel: \startCode > data Numerus = Singular | Plural \stopCode Obige Zeile f"uhrt einen neuen Datentyp \type{Numerus} ein. Dieser ist {\em verschieden} von allen anderen Datentypen, d.h.~ein Wert vom Typ \type{Numerus} geh"ort keinem anderen Datentyp an. Wie sehen nun Werte dieses Datentyps aus? Es gibt zwei M"oglichkeiten, angedeutet durch den senkrechten Strich \type{|}, den man am besten als \quotation{oder} liest: entweder es ist ein \type{Singular} oder es ist ein \type{Plural}. Jede M"oglichkeit definiert einen sogenannte \type{Konstruktor} f"ur den Datentyp. Konstruktoren sind spezielle Funktionen, die dazu dienen, Werte des jeweiligen Datentyps zu erzeugen. Wenn wir das Modul laden, k"onnen wir die Typen der Konstruktoren erfragen: \startHaskell Tag7> :t Singular Numerus Tag7> :t Plural Numerus Tag7> :t [Singular,Singular,Plural] [Numerus] \stopHaskell Wir sehen, da"s \type{Singular} und \type{Plural} selber Werte des Typs \type{Numerus} sind, und da"s wir mit ihnen komplexere Werte aufbauen k"onnen, indem wir sie zum Beispiel in eine Liste stecken. Warum sollten wir einen Typ wie \type{Numerus} deklarieren wollen? Wir k"onnten doch auch ganz einfach \type{0} und \type{1} nehmen, um Singular und Plural zu unterscheiden, oder \type{False} und \type{True}, oder gar die Strings \type{"Singular"} und \type{"Plural"}. Erstes Argument: Spezielle Typen dienen der Selbstdokumentation des geschriebenen Codes. Wie wir gesehen haben, ist das Definieren von Typen nicht aufwendig. Eine Zeile! Daf"ur k"onnen wir dann mit \quotation{sprechenden} Namen wie \type{Singular} oder \type{Plural} arbeiten, wenn unsere Anwendung tats"achlich etwas damit zu tun hat, und wir k"onnen diese Werte von anderen, \quotation{echten} Wahrheitswerten wie etwa Resultaten von Vergleichen unterscheiden. Zweites Argument: Nicht nur wir k"onnen den Code besser verstehen, wenn wir einen eigenen Typ verwenden, auch der Compiler kann das! Wie bereits erw"ahnt, \type{Numerus} ist ein Typ, der von anderen Typen verschieden ist. Wir laufen also nicht Gefahr, einen \type{Numerus} \quotation{aus Versehen} in einer \type{if}-Abfrage als Bedingung einzusetzen, weil der Compiler das abfangen w"urde, w"ahrend wir, wenn wir \type{Bool} als Representation n"ahmen, davor nicht sicher w"aren. Gegen \type{Integer} oder \type{String} als Representation spricht zudem, da"s diese Typen viel mehr Werte umfassen, und wir jedesmal, wenn wir eine Berechnung auf der Basis von einem Numerus durchf"uhren wollen, sicherstellen m"ussen, da"s der ihn representierende Integer oder String tats"achlich die richtige Form hat (also \type{0} oder \type{1} ist bzw.~\type{"Singular"} oder \type{"Plural"}). Wenn wir nun jedoch tats"achlich eine Funktion schreiben wollen, die etwas unter Verwendung eines \type{Numerus} macht, geraten wir in Schwierigkeiten. Nehmen wir an, wir wollen eine (stark vereinfachte) Funktion schreiben, die die dritte Personsform eines Verbs ermittelt. Diese bekommt den Stamm des Verbs als String und einen \type{Numerus}, und sie liefert am Ende die korrekte Form, wiederum als String, also: \startCode > drittePerson :: String -> Numerus -> String \stopCode Falls Singular gefragt ist, wollen wir ein \quotation{t} an den Stamm h"angen, andernfalls ein \quotation{en}. Aber wir haben keine M"oglichkeit, den Wert vom Typ \type{Numerus} zu analysieren. Hier kommt \quotation{pattern matching} ins Spiel: Das \type{case}-Konstrukt in Haskell erm"oglicht es uns, verschiedene Konstruktoren eines Typs voneinander zu unterscheiden: \startCode > drittePerson stamm num = > case num of > { Singular -> stamm ++ "t" > ; Plural -> stamm ++ "en" > } \stopCode Sowohl \type{case} als auch \type{of} sind Schl"usselworte, die den Ausdruck einrahmen, der analysiert werden soll. Danach folgen mehrere F"alle, die jeweils aus einem \quotation{Muster} und einem Ausdruck bestehen. Muster und Ausdruck sind dabei wiederum jeweils durch \type{->} voneinander getrennt. In diesem Fall gibt es also zwei F"alle mit den Mustern \type{Singular} und \type{Plural}. Haskell w"ahlt den ersten Fall, dessen Muster auf den analysierten Wert pa"st (daher der Name \quotation{pattern matching}). (Wir verwenden ab jetzt den Anglizismus \quotation{Pattern} f"ur das Wort Muster.) Damit verh"alt sich die Funktion nun wie erwartet, aber nat"urlich nicht perfekt: \startHaskell Tag7> drittePerson "geh" Singular "geht" Tag7> drittePerson "lauf" Plural "laufen" Tag7> drittePerson "lauf" Singular "lauft" \stopHaskell Wie Haskell uns schon erlaubt, Lambda-Abstraktionen in die Deklaration zu integrieren und uns ein explizites Verwenden von \type{\} zu ersparen, ist es auch m"oglich, das \type{case}-Konstrukt in die Funktionsdeklaration direkt mit aufzunehmen, indem wir einfach mehrere Funktionsdefinitionen schreiben, eine f"ur jeden Fall: \startCode > zweitePerson :: String -> Numerus -> String > zweitePerson stamm Singular = stamm ++ "t" > zweitePerson stamm Plural = stamm ++ "en" \stopCode Jeder Variablenname, der in einer Definition gebunden wird, kann also alternativ durch ein Pattern ersetzt werden. Eine Funktionsdefinition kann aus beliebig vielen Teilen bestehen. Der erste Fall, der pa"st (und nur der erste), wird ausgef"uhrt. Zur"uck zu den Datentypen: Wir f"uhren nun einen zweiten Datentyp ein, einen, mit dem man bin"are B"aume repr"asentieren kann, die an den Bl"attern Elemente haben. Wie schon bei Listen wollen wir, da"s alle Elemente vom gleichen Typ sind, aber der Typ soll ansonsten nicht n"aher bestimmt sein. \startCode > data BinTree a = Node (BinTree a) (BinTree a) | Leaf a \stopCode Wieder gibt es zwei M"oglichkeiten (durch den einen vertikalen Strich getrennt), und die Konstruktoren in diesem Falle hei"sen \type{Node} und \type{Leaf}. Diesmal haben jedoch sowohl der Datentyp selbst als auch die Konstruktoren Argumente. Der Baum-Datentyp ist parametrisiert mit dem Typ seiner Elemente, repr"asentiert durch die Typvariable \type{a}. Ein Baum kann {\em entweder} eine bin"are Verzweigung (\type{Node}) sein, die aus zwei Unterb"aumen besteht (daher die beiden Argumente von \type{Node}, beide wieder vom Typ \type{BinTree a}), {\em oder} er besteht lediglich aus einem Blatt, und da wir gesagt haben, da"s die Bl"atter Elemente enthalten sollten, hat das Blatt ein Argument vom Elementtyp \type{a}. Wieder k"onnen wir den Interpreter zur Best"atigung nach den Typen fragen: \startHaskell Tag7> :t Node forall a. BinTree a -> BinTree a -> BinTree a Tag7> :t Leaf forall a. a -> BinTree a Tag7> :t Node (Node (Leaf "a") (Leaf "b")) (Leaf "42") BinTree [Char] \stopHaskell Wir sehen, da"s beide Konstruktoren in der Tat Bin"arb"aume erzeugen und da"s die Argumente der Konstruktoren in der Typdeklaration in Funktionsargumente umgewandelt werden. Die dritte Eingabe zeigt einen Beispielbaum mit Strings als Elemente in den Bl"attern. Wenn wir nun eine Funktion per \quotation{pattern matching} auf bin"aren B"aumen definieren, dann k"onnen wir f"ur die Argumente der Konstruktoren wieder Variablen einf"uhren: \startCode > countLeaves :: BinTree a -> Integer > countLeaves (Leaf x) = 1 > countLeaves (Node l r) = countLeaves l + countLeaves r \stopCode Obige Funktion z"ahlt die Anzahl Bl"atter in einem Baum (mit beliebigem Elementtyp). Falls der Baum ein Blatt ist, dann hat er genau ein Blatt. Falls er eine Verzweigung ist, dann z"ahlen wir die Bl"atter in beiden Unterb"aumen und summieren sie. Die Variablen \type{l} und \type{r} sind Bestandteil des zweiten Patterns und werden an die Unterb"aume gebunden. \startAufgabe Schreibe eine Funktion \type{flattenBinTree :: BinTree a -> [a]}, die alle Bl"atter \quotation{von links nach rechts} in einer Liste aufsammelt. \startHaskell Flatten> flattenBinTree (Node (Node (Leaf "a") (Leaf "b")) (Leaf "42")) ["a","b","42"] it :: [[Char]] \stopHaskell \stopAufgabe Die meisten Haskell-Datentypen, die wir bislang kennengelernt haben, haben syntaktische Besonderheiten. Dennoch schadet es nicht, sie unter dem Gesichtspunkt zu betrachten, da"s man sie als eigene Datentypen definieren wollte. Beginnen wir mit Wahrheitswerten. Diese sind in der Tat einfach als \startCode data Bool = False | True \stopCode definiert. Folglich sind \type{False} und \type{True} auch Konstruktoren und k"onnen in Patterns verwendet werden. Womit sich auch die Frage, die sich vielleicht schon mancher gestellt hat, kl"art: Konstruktoren beginnen immer mit einem Gro"sbuchstaben, genau wie Typnamen. Es ist sogar erlaubt, da"s Konstruktoren und Typnamen sich "uberschneiden, es kann also einen Konstruktor geben, der genauso hei"st wie ein Typ. Trotzdem sind es zwei verschiedene Dinge: ein Konstruktor ist eine Funktion und als solches ein Ausdruck und {\em hat} einen Typ. Ein Typ hingegen {\em ist} ein Typ. Einzelne Zeichen (vom Typ \type{Char}) sind im Grunde nichts weiter als eine Aufz"ahlung aller m"oglichen Zeichen, etwa so \startCode data Char = ... | '!' | '"' | '#' | '$' | '%' | ... | 'A' | 'B' | 'C' | 'D' | 'E' | ... | 'a' | 'b' | 'c' | 'd' | 'e' | ... | ... \stopCode Im Prinzip also spielen die einzelnen Zeichen allesamt die Rolle von ziemlich vielen, aber immer noch endlich vielen Konstruktoren. Und in der Tat -- auch Zeichen k"onnen als Pattern verwendet werden. Bei Integers ist es "ahnlich. Hier ist die Anzahl der Werte prinzipiell unbegrenzt, aber auch sie k"onnen als Typ mit unendlich vielen Konstruktoren -- alle ohne Argumente -- aufgefa"st werden: \startCode data Integer = ... | -2 | -1 | 0 | 1 | 2 | ... \stopCode Und daher sind auch Integer-Literale in der Rolle von Konstruktoren und k"onnen in Patterns auftreten. Die Fakult"atsfunktion aus den "Ubungen der letzten Funktion kann wie folgt geschrieben werden: \startCode > factorial :: Integer -> Integer > factorial 0 = 1 > factorial n = n * factorial (n-1) \stopCode Listen k"onnte man wie folgt mit Hilfe von \type{data} definieren: \startCode data [a] = [] | a : [a] \stopCode Dies ist syntaktisch nicht erlaubt, entspricht aber genau dem Verhalten von Listen. Der Listentyp hat einen Parameter, der zwischen die eckigen Klammern geschrieben wird. Er hat zwei Konstruktoren, n"amlich die leere Liste \type{[]} und den Cons-Operator \type{:}. Letzterer hat zwei Argumente, wie bekannt: \startHaskell Tag7> :t [] forall a. [a] Tag7> :t (:) forall a. a -> [a] -> [a] \stopHaskell Und nat"urlich k"onnen auch diese Konstruktoren in Patterns auftreten. Die bereits bekannten Funktionen |head|, |tail| und |null| zum Selektieren des Kopfes und Restes einer Liste bzw. zum "Uberpr"ufen, ob eine Liste leer ist, lassen sich mit Hilfe von \quotation{pattern matching} auf Listen einfach definieren (wir w"ahlen leicht modifizierte Namen, um unsere Varianten von den vordefinierten unterscheiden zu k"onnen): \startCode > head' :: [a] -> a > head' (x:xs) = x > tail' :: [a] -> [a] > tail' (x:xs) = xs > null' :: [a] -> Bool > null' [] = True > null' xs = False \stopCode \startAufgabe Schreibe eine Funktion \type{inssort :: [Integer] -> [Integer]}, die eine Liste von ganzzahligen Werten nach dem \quotation{insertion sort}-Verfahren aufsteigend sortiert. (Jedes andere Sortierverfahren ist auch in Ordnung.) Benutze \quotation{pattern matching}. Schreibe dazu zun"achst eine Hilfsfunktion \type{ins :: Integer -> [Integer] -> [Integer]}, die eine Zahl in eine bereits sortierte Liste an der richtigen Stelle einf"ugt. \startHaskell Inssort> ins 6 [1,4,7,10] [1,4,6,7,10] Inssort> inssort [7,1,6,4,10] [1,4,6,7,10] \stopHaskell \stopAufgabe Zum Abschlu"s dieser schon viel zu langen Lektion betrachten wir nochmal die Tupel. Hier kann man sich vorstellen, da"s jeder Tupeltyp (also f"ur jede Tupell"ange) durch ein eigenes \type{data} definiert ist: \startCode data (a,b) = (a,b) data (a,b,c) = (a,b,c) data (a,b,c,d) = (a,b,c,d) ... \stopCode Jeder Tupeltyp hat nur einen Konstruktor, mit spezieller Syntax f"ur die Argumente, die \quotation{in den Konstruktor eingebettet} werden. Au"serdem haben Tupeltypen eine aufsteigende Anzahl von Parametern. Letzlich bedeutet das, da"s auch die Tupelkonstruktoren in Patterns auftreten k"onnen. Die Funktionen \type{fst} und \type{snd} zum Selektieren der Komponenten, und auch die bereits in den Aufgaben implementierte Funktion \type{swap} zum Vertauschen der Komponenten lassen sich so definieren (wir w"ahlen wiederum leicht modifizierte Namen): \startCode > fst' :: (a,b) -> a > fst' (x,y) = x > snd' :: (a,b) -> b > snd' (x,y) = y > swap' :: (a,b) -> (b,a) > swap' (x,y) = (y,x) \stopCode \startLernziele \item In Haskell k"onnen mit dem \type{data}-Schl"usselwort auf einfache Weise neue Datentypen definiert werden. (Die genauen M"oglichkeiten werden wir aber noch im Detail besprechen.) \item Haskell erlaubt \quotation{pattern matching} mittels \type{case}-Konstrukt. Verschiedene F"alle k"onnen unterschieden werden durch verschiedene Pattern. Pattern bestehen aus einer Mischung aus Variablennamen und {\em Konstruktoren}. Wenn der zu analysierende Wert vom richtigen Konstruktor ist, dann werden die Variablennamen an die Argumente des Konstruktors gebunden. \item Auch in Funktionsdefinitionen k"onnen statt Variablennamen f"ur die Argumente Pattern benutzt werden. \item Auch die Haskell-Basistypen haben Konstruktoren und k"onnen deshalb in Patterns verwendet werden. \stopLernziele \stoptext \stopproduct