Porovnávání vzorů je kontrola přítomnosti složek daného vzoru. Na rozdíl od rozpoznávání vzorů je vzor pevně specifikován. Takový vzor se obvykle týká buď sekvencí, nebo stromových struktur. Porovnávání vzorů se používá ke kontrole, zda věci mají požadovanou strukturu, k nalezení příslušné struktury, k vyhledání odpovídajících částí a k nahrazení odpovídající části něčím jiným.
Vzory sekvencí (nebo konkrétně textových řetězců) se často popisují pomocí regulárních výrazů (tj. zpětně) a porovnávají se pomocí příslušných algoritmů. Sekvence lze také chápat jako stromy větvící se pro každý prvek na příslušný prvek a zbytek sekvence, nebo jako stromy, které se okamžitě větví na všechny prvky.
Stromové vzory lze v programovacích jazycích použít jako obecný nástroj pro zpracování dat na základě jejich struktury. Některé funkcionální programovací jazyky, jako je Haskell, ML a jazyk symbolické matematiky Mathematica, mají speciální syntaxi pro vyjádření stromových vzorů a jazykovou konstrukci pro podmíněné provádění a získávání hodnot na jejím základě. Z důvodů jednoduchosti a efektivity tyto stromové vzory postrádají některé vlastnosti, které jsou k dispozici v regulárních výrazech. V závislosti na jazycích lze porovnávání vzorů použít pro argumenty funkcí, v pádových výrazech, vždy, když jsou vázány nové proměnné, nebo ve velmi omezených situacích, například pouze pro sekvence v přiřazení v jazyce Python. Často je možné zadat alternativní vzory, které se zkoušejí jeden po druhém. Při porovnávání vzorů lze využívat stráže.
Jazyky pro přepisování termínů se spoléhají na porovnávání vzorů, které je základním způsobem, jakým se program vyhodnocuje do výsledku. Porovnávání vzorů je nejvýhodnější, když jsou základní datové struktury co nejjednodušší a nejpružnější. To platí zejména pro jazyky se silným symbolickým přídechem. V symbolických programovacích jazycích jsou vzory stejným typem dat jako všechno ostatní, a proto je lze zadávat jako argumenty funkcím.
Nejjednodušším vzorem při porovnávání vzorů je explicitní hodnota nebo proměnná. Jako příklad uveďme jednoduchou definici funkce v syntaxi jazyka Haskell (parametry funkce nejsou v závorkách, ale jsou odděleny mezerami, = není přiřazení, ale definice):
Zde je 0 vzorem jedné hodnoty. Kdykoli je funkci f zadána jako argument hodnota 0, vzor se shoduje a funkce vrací hodnotu 1. S jakýmkoli jiným argumentem shoda, a tedy i funkce, selže. Protože syntaxe podporuje alternativní vzory v definicích funkcí, můžeme pokračovat v definici a rozšířit ji tak, aby přijímala více obecných argumentů:
První n je zde vzor jediné proměnné, který bude odpovídat naprosto libovolnému argumentu a naváže jej na jméno n, které bude použito ve zbytku definice. V Haskellu se (na rozdíl přinejmenším od Hope) vzory zkoušejí v pořadí, takže první definice platí i ve velmi specifickém případě, kdy je vstupem 0, zatímco pro jakýkoli jiný argument funkce vrátí n * f (n-1), přičemž n je argument.
Zástupný vzor (často psaný jako _) je také jednoduchý: stejně jako jméno proměnné odpovídá libovolné hodnotě, ale neváže hodnotu na žádné jméno.
Složitější vzory lze sestavit z primitivních vzorů z předchozího oddílu, obvykle stejným způsobem, jako se hodnoty sestavují kombinací jiných hodnot. Rozdíl je pak v tom, že u proměnných a zástupných částí se vzor nesestavuje z jedné hodnoty, ale odpovídá skupině hodnot, které jsou kombinací konkrétních prvků a prvků, které se mohou v rámci struktury vzoru měnit.
Vzor stromu popisuje část stromu tak, že začíná uzlem, určuje některé větve a uzly a některé ponechává neurčené pomocí proměnné nebo zástupného vzoru. Může pomoci představa abstraktního syntaktického stromu programovacího jazyka a algebraických datových typů.
Následující řádek definuje v jazyce Haskell algebraický datový typ Color, který má jediný datový konstruktor ColorConstructor, který obsahuje celé číslo a řetězec.
Konstruktor je uzel ve stromu a celé číslo a řetězec jsou listy ve větvích.
Když chceme napsat funkce, které z Barvy udělají abstraktní datový typ, chceme napsat funkce pro rozhraní s datovým typem, a tedy chceme z datového typu získat nějaká data, například jen řetězec nebo jen celočíselnou část Barvy.
Pokud předáme proměnnou typu Color, jak můžeme z této proměnné získat data? Například pro funkci, která má získat celočíselnou část proměnné Color, můžeme použít jednoduchý stromový vzor a zapsat:
Filtrování dat pomocí vzorů
K filtrování dat určité struktury lze použít porovnávání vzorů. Například v Haskellu lze pro tento druh filtrování použít porozumění seznamu:
Porovnávání vzorů v systému Mathematica
V systému Mathematica existuje pouze strom, který je vyplněn symboly. V dosud používané syntaxi jazyka Haskell by to mohlo být definováno takto
Příklad stromu by pak mohl vypadat takto
V tradiční, vhodnější syntaxi se symboly zapisují tak, jak jsou, a úrovně stromu se reprezentují pomocí [], takže například a[b,c] je strom s a jako rodičem a b a c jako potomky.
Vzor v systému Mathematica spočívá v tom, že na pozice v tomto stromu umístíte znak „_“. Například vzor
Bude odpovídat prvkům jako A, A nebo obecněji A[x], kde x je libovolná entita. V tomto případě je A konkrétní prvek, zatímco _ označuje část stromu, kterou lze měnit. Symbol připojený k _ váže shodu na toto jméno proměnné, zatímco symbol připojený k _ omezuje shodu na uzly tohoto symbolu.
Funkce Mathematica Cases filtruje prvky prvního argumentu, které odpovídají vzoru v druhém argumentu:
Porovnávání vzorů se vztahuje na strukturu výrazů. V níže uvedeném příkladu,
protože pouze tyto prvky budou odpovídat výše uvedenému vzoru a[b[_],_].
V systému Mathematica je také možné extrahovat struktury, které vznikají v průběhu výpočtu, bez ohledu na to, jak a kde se objevují. Funkci Trace lze použít ke sledování výpočtu a vracení prvků, které vznikly a odpovídají vzoru. Například Fibonacciho posloupnost můžeme definovat jako
Pak si můžeme položit otázku: Jaká je posloupnost rekurzivních Fibonacciho volání?
vrací strukturu, která představuje výskyty vzoru fib[_] ve výpočetní struktuře:
V symbolických programovacích jazycích je snadné mít vzory jako argumenty funkcí nebo jako prvky datových struktur. Důsledkem toho je možnost používat vzory k deklarativnímu vytváření výroků o částech dat a k pružnému instruování funkcí, jak mají pracovat.
K vytvoření efektivnější verze kódu lze například použít funkci Compile systému Mathematica. V následujícím příkladu na detailech nijak zvlášť nezáleží; důležité je, že podvýraz {{com[_], _Integer}} dává funkci Compile pokyn, že výrazy tvaru com[_] lze pro účely kompilace považovat za celá čísla:
Tímto způsobem fungují i poštovní schránky v Erlangu.
Porovnávání vzorů a řetězce
Zdaleka nejběžnější forma porovnávání vzorů zahrnuje řetězce znaků. V mnoha programovacích jazycích se k reprezentaci regulárních výrazů, což jsou vzory popisující řetězcové znaky, používá zvláštní syntaxe řetězců.
Nicméně je možné provádět určité porovnávání řetězců v rámci stejného rámce, který byl popsán v tomto článku.
V systému Mathematica jsou řetězce reprezentovány jako stromy kořene StringExpression a všech znaků v pořadí jako potomků kořene. Proto je k přiřazení „libovolného množství koncového znaku“ potřeba nový zástupný znak ___ na rozdíl od _, který by odpovídal pouze jedinému znaku.
V jazyce Haskell a obecně ve funkcionálních programovacích jazycích jsou řetězce reprezentovány jako funkcionální seznamy znaků. Funkční seznam je definován jako prázdný seznam nebo prvek vytvořený na základě existujícího seznamu. V syntaxi jazyka Haskell:
Struktura pro seznam s některými prvky je tedy element:list. Při porovnávání vzorů tvrdíme, že určitý kus dat odpovídá určitému vzoru. Například ve funkci:
tvrdíme, že první prvek argumentu head se nazývá element, a funkce jej vrací. Víme, že se jedná o první prvek, protože vzhledem ke způsobu definování seznamů se jedná o jeden prvek zkonstruovaný na seznam. Tento jediný prvek musí být první. Prázdný seznam by vzoru vůbec neodpovídal, protože prázdný seznam nemá hlavičku (první zkonstruovaný prvek).
V příkladu nemáme pro seznam žádné využití, takže ho můžeme ignorovat, a tak funkci zapsat:
Ekvivalentní transformace v systému Mathematica je vyjádřena takto
Například v systému Mathematica,
bude odpovídat řetězci, který obsahuje dva znaky a začíná písmenem „a“.
Stejný vzor v jazyce Haskell:
Symbolické entity lze zavést k reprezentaci mnoha různých tříd relevantních vlastností řetězce. Například,
bude odpovídat řetězci, který se skládá nejprve z písmene a poté z čísla.
Hlavní výhodou symbolické manipulace s řetězci je to, že může být zcela integrována do zbytku programovacího jazyka a nepředstavuje samostatnou účelovou podjednotku. Celou sílu jazyka lze využít k sestavování samotných vzorů nebo k analýze a transformaci programů, které je obsahují.
Tato část je vsuvka. Můžete pomoci tím, že ji doplníte.
První počítačové programy, které používaly porovnávání vzorů, byly textové editory. Ken Thompson v Bell Labs rozšířil funkce vyhledávání a nahrazování editoru QED o regulární výrazy. Mezi první programovací jazyky s konstrukcemi pro porovnávání vzorů patří SNOBOL z roku 1962, NPL z roku 1977 a KRC z roku 1981.
Tato část je vsuvka. Můžete pomoci tím, že ji doplníte.