Patroonvergelijking

In de informatica wordt onder patroonvergelijking (Engels: pattern matching) het herkennen van een specifiek patroon in data verstaan. Het te herkennen patroon wordt hierbij eenduidig gespecificeerd, en bestaat uit (een samenstelling van) simpele patronen. Patroonvergelijking wordt gebruikt om te testen of data een specifieke structuur heeft (bijvoorbeeld het controleren van een e-mailadres), om data in kleinere eenheden te verdelen (bijvoorbeeld het parsen van een tekst) of om de gevonden data te vervangen door iets anders. Een veelgebruikte vorm van patroonvergelijking is het zoeken in een tekst naar patronen die gespecificeerd zijn als reguliere expressies. Patroonvergelijking kan echter ook toegepast worden op bomen, lijsten en andere samengestelde structuren.

Boompatronen (Engels: tree patterns) kunnen in programmeertalen worden gebruikt om data te verwerken op basis van de structuur van deze data. Zo hebben sommige functionele programmeertalen (zoals Haskell en ML) een speciale syntaxis voor het beschrijven van boompatronen en taalconstructies om delen hiervan te inspecteren en te bewerken. Afhankelijk van de programmeertaal kan patroonvergelijking toegepast worden op functieparameters, in voorwaardelijke expressies of alleen wanneer variabelen gedefinieerd worden.

Simpele patronen

Een simpel patroon is een patroon dat niet is samengesteld uit andere (eenvoudiger) patronen. Voorbeelden van simpele patronen zijn getallen en een lege lijst. In reguliere expressies is een simpel patroon een enkel karakter.

Een simpel patroon valt meestal samen met de waarde die het voorstelt: een patroon dat uit een lege lijst bestaat accepteert slechts één waarde: de lege lijst. Een patroon dat uit een getal bestaat accepteert alleen dát getal^[1]. Een uitzondering hierop is het jokerteken (ook wel wildcard genoemd). Hoewel het een simpel patroon is (het is niet samengesteld uit eenvoudiger patronen), accepteert een jokerteken iedere waarde, ongeacht de structuur.

De volgende functie in OCaml test of de waarde van de opgegeven parameter x overeenkomt met het simpele patroon "3":

   let f x = match x with
  | 3 -> true
  | _ -> false
   ;;

Merk op dat een jokerteken in OCaml (en bijvoorbeeld ook in Haskell) weergegeven wordt als een liggend streepje (_). In reguliere expressies heeft het jokerteken geen eigen notatie, maar hetzelfde effect kan op verschillende manieren bereikt worden (bijvoorbeeld ".*").^[2]

Dit is een nogal omslachtige manier om te testen of x gelijk is aan 3. Simpele patronen zijn op zichzelf dan ook niet erg interessant. De kracht van patroonvergelijking ligt in het gebruik van samengestelde patronen.

Samengestelde patronen

Samengestelde patronen bestaan uit meerdere patronen. De samenstellende patronen kunnen op hun beurt weer simpel of samengesteld zijn. In tegenstelling tot simpele patronen accepteert een samengesteld patroon niet één waarde, maar een verzameling van waarden. Deze verzameling kan eindig zijn (bijvoorbeeld een willekeurig karakter) of oneindig (bijvoorbeeld een positief geheel getal).

De manier waarop patronen gecombineerd kunnen worden, en de bijbehorende notatie, hangt af van de programmeertaal.

Voorbeeld: lijsten in Haskell

Haskell maakt, zoals de meeste functionele programmeertalen, veelvuldig gebruik van patroonvergelijking. Zo is patroonvergelijking de enige manier in Haskell om waarden uit lijsten en tupels te selecteren. In Haskell specificeert de notatie x:y een nieuw patroon, waarvoor geldt: x:y is een lijst, waarbij x het eerste element van de lijst is en y de rest van de lijst. Om het eerste element van een lijst te verkrijgen kunnen we de volgende functie definiëren:

 item1 (x:xs) = x

Omdat de waarde van xs (de rest van de lijst) onbelangrijk is, kunnen we ook een wildcard gebruiken:

 item1 (x:_) = x

Om het derde element van een lijst te selecteren gebruiken we de volgende functie:

 item3 (_:_:x:_) = x

Om een willekeurig element uit een lijst te selecteren definiëren we een recursieve definitie waarbij we abstraheren over de index van het te selecteren element:

 item 1 (x:xs) = x
 item index [] = error "Index out of bounds"
 item index (x:xs) = item (index-1) xs

De Haskell-operator !! die een element uit een lijst selecteert is op deze manier, door middel van patroonvergelijking, gedefinieerd.^[3]

Voorbeeld: Prolog

Prolog maakt bij het beantwoorden van query's gebruik van patroonvergelijking (dit proces wordt unification genoemd).^[4] Als voorbeeld nemen we een database die uit één clause bestaat:

 wissel(foo(X, Y), foo(Y, X)).

Het predicaat wissel kan gebruikt worden om de argumenten van foo om te draaien. Wanneer we de volgende query opgeven:

 wissel(foo(1, 2), Z).

antwoordt Prolog met

 Z = foo(2, 1)

Prolog komt tot dit resultaat door het patroon van de query te vergelijken met het patroon van de clauses in de database (in dit geval is er maar één clause):

 query: wissel(foo(1, 2), Z )
 clause: wissel(foo(X, Y), foo(Y, X))

Omdat de predicaten hetzelfde zijn, worden vervolgens hun argumenten vergeleken:

 query: 1: foo(1,2), 2: Z
 clause: 1: foo(X,Y), 2: foo(Y,X)

De eerste argumenten hebben weer hetzelfde patroon, en daarom krijgt variabele X de waarde 1 en variabele Y de waarde 2:

 X=1, Y=2
 query: 1: foo(1,2), 2: Z
 clause: 1: foo(1,2), 2: foo(2,1)

Nu de eerste argumenten gelijk zijn, worden de tweede argumenten vergeleken, waarbij Z gelijk wordt gesteld aan foo(2,1):

 X=1, Y=2, Z=foo(2,1)
 query: 1: foo(1,2), 2: foo(2,1)
 clause: 1: foo(1,2), 2: foo(2,1)

En daarmee is het antwoord bereikt: wissel(foo(1, 2), Z) heeft hetzelfde patroon als wissel(foo(X, Y), foo(Y, X)) wanneer Z gelijk is aan foo(2,1).

Zie ook

Externe links

(en) A Gentle Introduction to Haskell: Patterns
(en) The Implementation of Functional Programming Languages, pages 53-103 Simon Peyton Jones, published by Prentice Hall, 1987.
(en) Developing Applications With OCaml: Pattern Matching

Bronnen, noten en/of referenties

↑ In plaats van "accepteren" is het gebruikelijk om de Engelse term match te gebruiken. "Het patroon accepteert de lege lijst" wordt dan "Het patroon matcht de lege lijst".
↑ Merk op dat een enkele punt (.) geen jokerteken is omdat het slechts één karakter matcht. Het patroon ".*" is eveneens geen jokerteken omdat het een samengesteld patroon is.

↑ De exacte definitie is te vinden in Prelude.hs en is als volgt:

 (!!) :: [a] -> Int -> a<br />
 xs !! n | n<0 = error "Prelude.!!: negative index"<br />
 [] !! _ = error "Prelude.!!: index too large"<br />
 (x:_) !! 0 = x<br />
 (_:xs) !! n = xs !! (n-1)<br />

↑ Prolog under the hood

[1] In plaats van "accepteren" is het gebruikelijk om de Engelse term match te gebruiken. "Het patroon accepteert de lege lijst" wordt dan "Het patroon matcht de lege lijst".

[2] Merk op dat een enkele punt (.) geen jokerteken is omdat het slechts één karakter matcht. Het patroon ".*" is eveneens geen jokerteken omdat het een samengesteld patroon is.

[3] De exacte definitie is te vinden in Prelude.hs en is als volgt:

(!!) :: [a] -> Int -> a<br /> xs !! n | n<0 = error "Prelude.!!: negative index"<br /> [] !! _ = error "Prelude.!!: index too large"<br /> (x:_) !! 0 = x<br /> (_:xs) !! n = xs !! (n-1)<br />

[4] Prolog under the hood

[1]

[2]

[3]

[4]