10 Pattern Matching

Viele Funktionen konsumieren Daten, die einen Summentyp oder einen algebraischen Datentyp (also eine Mischung aus Summen- und Produkttypen (Datendefinition durch Alternativen und Zerlegung: Algebraische Datentypen) mit einer Summe "ganz oben" haben.

Häufig (und gemäß unseres Entwurfsrezepts) sehen solche Funktionen so aus, dass zunächst einmal unterschieden wird, welche Alternative gerade vorliegt, und dann wird (ggf. in Hilfsfunktionen) auf die Komponenten des in der Alternative vorliegenden Produkttypen zugegriffen.

Mit Pattern Matching können solche Funktionen mit deutlich reduziertem Aufwand definiert werden. Pattern Matching hat zwei Facetten: 1) Es definiert implizit eine Bedingung, analog zu den Bedingungen in den cond Klauseln oben. 2) Es definiert Namen, die statt der Projektionen ((first l) und (rest l) im Beispiel) verwendet werden können.

Pattern Matching kann auf allen Arten von Summentypen verwendet werden. Insbesondere ist es nicht auf rekursive Typen wie Listen oder Bäume beschränkt.

10.1 Pattern Matching am Beispiel

Um Unterstützung für Pattern Matching zu bekommen, verwenden wir das Teachpack 2htdp/abstraction. Fügen Sie an Anfang ihres Programms daher diese Anweisung ein:

(require 2htdp/abstraction)

Das folgende Beispiel zeigt, wie das match Konstrukt verwendet werden kann.

(define (f x)

(match x

[7 8]

["hey" "joe"]

[(list 1 y 3) y]

[(cons a (list 5 6)) (add1 a)]

[(posn 5 5) 42]

[(posn y y) y]

[(posn y z) (+ y z)]

[(cons (posn 1 z) y) z]

[(? cons?) "nicht-leere Liste"]))

Hier sind einige Beispiele, die das Verhalten des match Konstrukts illustrieren.

> (f 7)

8

> (f "hey")

"joe"

> (f (list 1 2 3))

2

> (f (list 4 5 6))

5

> (f (make-posn 5 5))

42

> (f (make-posn 6 6))

6

> (f (make-posn 5 6))

11

> (f (list (make-posn 1 6) 7))

6

> (f (list 99 88))

"nicht-leere Liste"

> (f 42)

match: no matching clause for 42

Jede Klausel in einem match Ausdruck beginnt mit einem Pattern. Ein Pattern kann ein Literal sein, wie in den ersten beiden Klauseln (7 und "hey"). In diesem Fall ist das Pattern lediglich eine implizite Bedingung: Wenn der Wert, der gematcht wird (im Beispiel x), gleich dem Literal ist, dann ist der Wert des Gesamtausdrucks der der rechten Seite der Klausel (analog zu cond).

Interessant wird Pattern Matching dadurch, dass auch auf Listen und andere algebraische Datentypen "gematcht" werden kann. In den Pattern dürfen Namen vorkommen (wie das y in (list 1 y 3) ; diese Variablen sind im Unterschied zu Strukturnamen oder Literalen keine Bedingungen, sondern sie dienen zur Bindung der Namen an den entsprechenden Teil der Struktur.

Allerdings können Namen zur Bedingung werden, wenn sie mehrfach im Pattern vorkommen. Im Beispiel oben ist dies der Fall im Pattern (posn y y). Dieses Pattern matcht nur dann, wenn x eine posn ist und beide Komponenten den gleichen Wert haben.

Falls mehrere Pattern gleichzeitig matchen, so "gewinnt" stets das erste Pattern, welches passt (analog dazu wie auch bei cond stets die erste Klausel, deren Kondition true ergibt, "gewinnt". Daher ergibt beispielsweise (f (make-posn 5 5)) im Beispiel das Ergebnis 42 und nicht etwa 5 oder 10.

Das vorletzte Pattern, (cons (posn 1 z) y), illustriert, dass Patterns beliebig tief verschachtelt werden können.

Im letzten Pattern, (? list?), sehen wir, dass auch Prädikatsfunktionen von Listen und Strukturen verwendet werden können, um zu überprüfen, was für eine Art von Wert wir gerade haben. Diese Art von Pattern bietet sich an, wenn man nur wissen möchte, ob der Wert, auf dem wir matchen, zum Beispiel eine Liste oder eine posn ist.

Pattern Matching ist in vielen Fällen eine sinnvolle Alternative zum Einsatz von cond Ausdrücken. Beispielsweise können wir mittels Pattern Matching die Funktion

(define (person-has-ancestor p a)

(cond [(person? p)

(or

(string=? (person-name p) a)

(person-has-ancestor (person-father p) a)

(person-has-ancestor (person-mother p) a))]

[else #false]))

aus Rekursive Datentypen umschreiben zu:

(define (person-has-ancestor p a)

(match p

[(person name father mother)

(or

(string=? name a)

(person-has-ancestor father a)

(person-has-ancestor mother a))]

[else #false]))

10.2 Pattern Matching allgemein

Wir betrachten die Syntax, Bedeutung und Reduktion von Pattern Matching.

10.2.1 Syntax von Pattern Matching

Um die syntaktische Struktur der match Ausdrücke zu definieren, erweitern wir die Grammatik für Ausdrücke aus Syntax von BSL wie folgt:

10.2.2 Bedeutung von Pattern Matching

Falls man einen Ausdruck der Form (match v [p-1 e-1] ... [p-n e-n]) hat, so kann man Pattern Matching verstehen als die Aufgabe, ein minimales i zu finden, so dass p-i auf v "matcht". Aber was bedeutet das genau?

Wir können Matching als eine Funktion definieren, die ein Pattern und einen Wert als Eingabe erhält und entweder "no match" oder eine Substitution zurückgibt. Eine Substitution ist ein Mapping \( \left[ x_1 := v_1, \ldots, x_n := v_n \right] \) von Namen auf Werte. Eine Substitution kann auf einen Ausdruck angewendet werden. Dies bedeutet, dass alle Namen in dem Ausdruck, die in der Substitution auf einen Wert abgebildet werden, durch diesen Wert ersetzt werden. Wenn \(e\) ein Ausdruck ist und \(\sigma\) eine Substitution, so schreiben wir \(e \sigma\) für die Anwendung von \(\sigma\) auf \(e\). Beispielsweise für \(\sigma = \left[ x := 1, y := 2 \right] \) und \(e = \mathtt{(+\ x\ y\ z)}\), ist

\[e \sigma = \mathtt{(+\ x\ y\ z)}\left[ x := 1, y := 2 \right] = \mathtt{(+\ 1\ 2\ z)}\]

Das Matching eines Werts auf ein Pattern ist nun wie folgt definiert:

\[\begin{aligned} \mathit{match}(v,v) & = \left[ \right] \\ \mathit{match}( \mathit{(name}\ p_1 \ldots p_n\mathtt{)}, \mathtt{<}\mathtt{make}\mathit{-name}\ v_1 \ldots v_n\mathtt{>}) & = \mathit{match}(p_1,v_1) \oplus \ldots \oplus \mathit{match}(p_n,v_n) \\ \mathit{match}( \mathtt{(}\mathtt{cons}\ p_1\ p_2\mathtt{)},\mathtt{<}\mathtt{cons}\ v_1\ v_2\mathtt{>}) & = \mathit{match}(p_1,v_1) \oplus \mathit{match}(p_2,v_2) \\ \mathit{match}(\mathtt{(}?\ \mathtt{name}?\mathtt{)}, <\mathtt{make}\mathit{-name} \ldots > \mathtt{)} & = \left[ \right] \\ \mathit{match}(x, v) & = \left[ x := v \right] \\ \mathit{match}(\ldots, \ldots) & = \mathit{no\ match\ } \text{in allen anderen Fällen} \\ \end{aligned}\]

Hierbei ist \(\oplus\) ein Operator, der Substitutionen kombiniert. Das Ergebnis von \(\sigma_1 \oplus \sigma_2\) ist "no match", falls \(\sigma_1\) oder \(\sigma_2\) "no match" sind oder \(\sigma_1\) und \(\sigma_2\) beide ein Mapping für den gleichen Namen definieren aber diese auf unterschiedliche Werte abgebildet werden.

\[\begin{aligned} \left[ x_1 := v_1, \ldots, x_k := v_k \right] \oplus \left[ x_{k+1} := v_{k+1}, \ldots, x_n := v_n \right] = \left[ x_1 := v_1, \ldots, x_n := v_n \right] \\ \ \ \text{ falls für alle } i,j \text{ gilt:} x_i = x_j \Rightarrow v_i = v_j. \end{aligned}\]

Beispiele: \[\begin{aligned} \mathit{match}(\mathtt{(posn\ x\ y)},\mathtt{<make-posn\ 3\ 4>}) = \left[ x := 3, y := 4 \right] \\ \end{aligned}\] \[\begin{aligned} \mathit{match}(\mathtt{(posn\ 3\ y)},\mathtt{<make-posn\ 3\ 4>}) = \left[y := 4 \right] \\ \end{aligned}\] \[\begin{aligned} \mathit{match}(\mathtt{x},\mathtt{<make-posn\ 3\ 4>}) = \left[x := \mathtt{<make-posn\ 3\ 4>} \right] \\ \end{aligned}\]

\[\begin{aligned} \mathit{match}(\mathtt{(cons\ (posn\ x\ 3)\ y)},\mathtt{<cons\ <make-posn\ 3\ 3>\ empty>}) = \left[x := \mathtt{3}, y := empty \right] \\ \end{aligned}\]

\[\begin{aligned} \mathit{match}(\mathtt{(cons\ (posn\ x\ x)\ y)},\mathtt{<cons\ <make-posn\ 3\ 4>\ empty>}) = \mathit{no\ match\ } \\ \end{aligned}\]

Beim Vergleich auf unterschiedliche Werte durch \(\oplus\) werden tatsächlich jedoch nicht die Werte direkt verglichen sondern die Funktion equal? zum Vergleich verwendet. Im derzeitigen Sprachlevel ist dieser Unterschied nicht relevant, doch wenn wir später Funktionen als Werte betrachten, so kann dies zu überraschenden Ergebnissen führen, da eigentlich gleiche Funktionen bezüglich der equal? Funktion nicht umbedingt gleich sind. Da das Vergleichen von Funktionen eine komplizierte Angelegenheit ist, wird in vielen Sprachen mit Pattern Matching nur sogenanntes "lineares" Pattern Matching unterstützt. Dies bedeutet, dass Pattern Variablen nur einmal im Pattern vorkommen dürfen; Patterns wie (posn x x) wären dann nicht erlaubt.

10.2.3 Reduktion von Pattern Matching

Wir erweitern die Grammatik des Auswertungskontextes so, dass der Ausdruck, auf dem gemacht wird, zu einem Wert reduziert werden kann. Alle anderen Unterausdrücke des match Ausdrucks werden nicht ausgewertet.

In der Reduktionsrelation verwenden wir nun die \(\mathit{match}\) Funktion von oben um zu entscheiden, ob ein Pattern matcht und um ggf. die durch das Pattern gebundenen Namen in dem dazugehörigen Ausdruck durch die entsprechenden Werte zu ersetzen.

(MATCH-YES): Falls in einem Ausdruck (match v [p-1 e-1] ... [p-n e-n]) gilt: match(p-1,v) = \(\sigma\) und e-1 \(\sigma\) = e, dann (match v [p-1 e-1] ... [p-n e-n]) → e.

(MATCH-NO): Falls hingegen match(p-1,v) = "no match", so gilt: (match v [p-1 e-1] ... [p-n e-n]) → (match v [p-2 e-2] ... [p-n e-n]).

Sind keine Patterns zum Matchen mehr übrig, so wird die Auswertung mit einem Laufzeitfehler abgebrochen, wie oben an dem (f 42) Beispiel illustriert. Dies wird in der Reduktionssemantik dadurch modelliert, dass die Auswertung "steckenbleibt", also nicht mehr weiter reduziert werden kann obwohl der Ausdruck noch kein Wert ist.

10.2.4 Pattern Matching Fallstricke

Es gibt einige Besonderheiten bgzl. des Verhaltens von Pattern Matching bei der Verwendung von Literalen, die möglicherweise zu Verwirrungen führen können.

Hier einige Beispiele:

> (match true [false false] [else 42])

#true

> (match true [#false false] [else 42])

42

> (match (list 1 2 3) [empty empty] [else 42])

'(1 2 3)

> (match (list 1 2 3) [(list) empty] [else 42])

42

Die ersten beiden Beispiele illustrieren, dass es wichtig ist, die boolschen Konstanten als #true und #false zu schreiben, wenn sie in Pattern vorkommen. Wenn man stattdessen false oder true schreibt, so werden diese als Namen interpretiert, die durch das Pattern Matching gebunden werden.

Die letzten beiden Beispiele zeigen, dass das gleiche Phänomen bei Listenliteralen auftritt. Schreiben Sie (list) und nicht empty wenn Sie auf die leere Liste matchen wollen.