other stuff - haskell

3. Pattern Matching und verzögerte Auswertung

Pattern Matching ist eine der zentralen Aufgaben von Haskell, da es für die Auswahl der zur konkreten Situation passenden Definition notwendig ist. Warum dies so ist und wie dies geschieht soll in diesem Abschnitt gezeigt werden. Außerdem werden kurz einige Aspekte von "Lazy Evaluation" zusammengestellt und "Lazy Patterns" vorgestellt.

3.1 Grundlagen des Pattern Matching

Bis hier wurden bereits einige Deklarationen verwendet, zu deren Verwendung Pattern Matching notwendig ist. Darunter waren z.B.: 

length []               = 0
length (y:ys)           = 1+length ys
fringe Leaf x           = [x]
So muss bei der Benutzung von length unterschieden werden, ob die angegebene Liste leer ist (in diesem Fall trifft die erste Definition zu) oder nicht (dann wird die zweite Definition verwendet). Ist ein Match erfolgreich, d.h. entspricht das konkret gegebene Muster den Anforderungen in der Definition, werden als "Seiteneffekt" die "formalen Parameter" (im Fall von fringe ist das x) an die konkreten Werte gebunden.

Man unterscheidet Patterns, die immer zu einem Match führen ("irrefutable patterns") und solche, bei denen das nicht der Fall ist ("refutable patterns"). In die erste Kategorie fallen z.B. formale Parameter von Funktionen wie add, in die zweite die drei oben angegebenen Beispiele.

Pattern Matching kann grundsätzlich zu drei Ergebnissen führen:

  • Erfolg ("succeed"). In diesem Fall werden die formalen Parameter gebunden und die Sache ist erledigt.
  • Misserfolg ("fail"). Das Muster passt nicht. Es wird mit der nächsten verfügbaren Definition fortgefahren.
  • Fehler ("diverge"). Bei der Auswertung eines aktuellen Parameters kam es zu einem Fehler. In diesem Fall wird das Programm abgebrochen.
Das Matching erfolgt "von links nach rechts, von oben nach unten". Das bedeutet, dass weiter oben angegebene Definitionen auch zuerst überprüft werden, innerhalb einer Definition wird von links nach rechts vorgegangen. Folgendes Beispiel soll dies verdeutlichen. Sei bot ein nicht wohldefinierter Ausdruck. Versucht man, (1,2) gegen (0,bot) zu matchen, führt dies zu einem fail, da die ersten Elemente der Tupel nicht übereinstimmen und der Match-Vorgang folglich mit einem Misserfolg abgebrochen wird. Matcht man (1,2) hingegen gegen (bot,0), so erhält man Divergenz, da beim Versuch, 1 mit bot zu vergleichen, letzteres nicht bestimmt werden kann.

3.2 As-Patterns und Wildcards

Bei As-Patterns und Wildcards handelt es sich um zwei Typen von Patterns, die immer zu einem Match führen.

As-Patterns dienen dazu, einem bestimmten Teil eines Patterns einen eigenen Namen zuzuordnen. Als Beispiel betrachte man folgende Funktionsdeklaration. 

f (y:ys)                = y:y:ys
Um die rechte Seite der Definition übersichtlicher zu machen, kann man ein As- Pattern benutzen. 
f s@(y:ys)              = y:s
Mittels @ wird dem als Struktur (y:ys) angegebenen Parameter ein eigener Name zugewiesen. Auch wenn (y:ys) als Pattern refutable ist, führt das As-Pattern formal immer zu einem Match.

Wildcards _ dienen dazu, auf das Binden eines formalen Parameters zu verzichten, wenn der entsprechende Teil eines Patterns nicht mehr benötigt wird. Sie können einerseits dazu verwendet werden, die Irrelevanz eines Teils des Patterns zu betonen. Andererseits führen sie aber auch dazu, dass die aktuellen Parameter an dieser Stelle nicht ausgewertet werden, wodurch diese auch nicht zu einem fail des Match beitragen können. Mit Hilfe einer Wildcard lässt sich die Definition der Funktion head auch so formulieren: 

head (y:_)              = y

3.3 Lazy Evaluation und Lazy Patterns

Bisher wurde auf verzögerte Auswertung oder Lazy Evaluation nicht explizit eingegangen. Dieses Konzept meint im Grunde nichts anderes, als dass Ausdrücke erst bei Bedarf ausgewertet, Datenstrukturen erst bei ihrer Verwendung angelegt werden. Die reine Definition etwa einer langen Liste bewirkt also noch keinen Speicherverbrauch.

Hier sollen nun exemplarisch drei für das Programmdesign wichtige Aspekte dieses Konzepts rekapituliert werden, bevor mit Lazy Patterns eine mit Pattern Matching zusammenhängende Spielart von Haskells "Laziness" vorgestellt wird.

  • Ausdrücke werden nur ausgewertet, wenn nötig. Definiert man z.B. eine einstellige konstante Funktion 
    const13 a               = 13
    so ist diese auch definiert, wenn es der übergebene Parameter nicht ist. 
    const13 1/0             ⇒ 13
  • Pattern Matching bricht in dem Moment ab, wo eine Nichtübereinstimmung gefunden wurde. 
    (1,2,3)==(0,1/0,3)      ⇒ False
(1,2,3)==(1,1/0,3) 	⇒ ⊥
    Hierbei steht ⊥ ("bottom") für einen Fehler.
  • Es ist möglich, unendliche Strukturen zu definieren. Definiert man sich z.B. eine Liste ganzer Zahlen 
    intlist i               = i:intlist (i+1)
    so kann man mit der Funktion take, die die ersten n Elemente einer Liste zurückliefert, die so konstruierte unendliche Folge tatsächlich benutzen. 
    take 5 (intlist 1)      ⇒ [1,2,3,4,5]
Eine Möglichkeit, die Auswertung von Ausdrücken beim Pattern Matching gezielt zu verzögern, bieten sogenannte Lazy Patterns. Ihre Funktion lässt sich am Besten an Hand eines Beispiels verdeutlichen.

Man betrachte ein System bestehend aus einem Client und einem Server. Der Client sendet Anfragen an den Server, der Server antwortet darauf. Die erste Anfrage wird dem Client vorgegeben (init), alle weiteren hängen von der jeweils letzten Antwort des Servers ab. Dies lässt sich in Haskell so formulieren. 

reqs                      = client init resps
resps                     = server reqs
client init (resp:resps)  = init : client (next resp) resps
server (req:reqs)         = process req : server reqs
Dabei müssen die Funktionen next und process natürlich geeignet definiert sein. Das offensichtliche Problem ist, dass beim ersten Aufruf von client der Server noch keine Antworten erzeugt haben kann, dass also (resp:resps) nicht zu einem Match führen kann. Dieses Problem lässt sich nun durch Lazy Patterns überwinden. durch ein Tilde ~ wird das entsprechende Pattern als lazy gekennzeichnet, was dazu führt, dass es unmittelbar zu einem Match führt und erst bei Verwendung überprüft wird. 
client init ~(resp:resps) = init : client (next resp) resps
Damit erhält reqs sein erstes Element, die Kommunikation wird wie zu erwarten angestoßen und Client und Server Tauschen bis in alle Ewigkeit Nachrichten aus.

<-zurück ^Inhalt ->weiter