Porovnávanie vzorov je kontrola prítomnosti zložiek daného vzoru. Na rozdiel od rozpoznávania vzorov je vzor pevne špecifikovaný. Takýto vzor sa zvyčajne týka buď sekvencií, alebo stromových štruktúr. Porovnávanie vzorov sa používa na kontrolu toho, či veci majú požadovanú štruktúru, na nájdenie príslušnej štruktúry, na získanie zhodných častí a na nahradenie zhodnej časti niečím iným.
Vzory sekvencií (alebo konkrétne textových reťazcov) sa často opisujú pomocou regulárnych výrazov (t. j. spätne) a porovnávajú sa pomocou príslušných algoritmov. Sekvencie možno tiež vnímať ako stromy vetviace sa pre každý prvok na príslušný prvok a zvyšok sekvencie alebo ako stromy, ktoré sa okamžite vetvia na všetky prvky.
Vzory stromov sa môžu používať v programovacích jazykoch ako všeobecný nástroj na spracovanie údajov na základe ich štruktúry. Niektoré funkcionálne programovacie jazyky, ako napríklad Haskell, ML a jazyk symbolickej matematiky Mathematica, majú špeciálnu syntax na vyjadrenie stromových vzorov a jazykovú konštrukciu na podmienené vykonávanie a získavanie hodnôt na jej základe. Z dôvodu jednoduchosti a efektívnosti týmto stromovým vzorom chýbajú niektoré funkcie, ktoré sú dostupné v regulárnych výrazoch. V závislosti od jazykov sa porovnávanie vzorov môže používať pre argumenty funkcií, v pádových výrazoch, vždy, keď sa viažu nové premenné, alebo vo veľmi obmedzených situáciách, napríklad len pre sekvencie v priradení v jazyku Python. Často je možné uviesť alternatívne vzory, ktoré sa skúšajú jeden po druhom. Pri porovnávaní vzorov možno využiť stráže.
Jazyky na prepisovanie termov sa spoliehajú na porovnávanie vzorov, ktoré je základným spôsobom vyhodnocovania programu do výsledku. Porovnávanie vzorov je najvýhodnejšie vtedy, keď sú základné dátové štruktúry čo najjednoduchšie a najflexibilnejšie. To platí najmä v jazykoch so silným symbolickým nádychom. V symbolických programovacích jazykoch sú vzory rovnakým druhom dátového typu ako všetko ostatné, a preto sa môžu zadávať ako argumenty funkcií.
Najjednoduchším vzorom pri porovnávaní vzorov je explicitná hodnota alebo premenná. Ako príklad si uveďme jednoduchú definíciu funkcie v syntaxi Haskellu (parametre funkcie nie sú v zátvorkách, ale sú oddelené medzerami, = nie je priradenie, ale definícia):
V tomto prípade je 0 vzorom jednej hodnoty. Vždy, keď sa ako argument zadá 0, vzor sa zhoduje a funkcia vráti 1. Pri akomkoľvek inom argumente porovnávanie, a teda aj funkcia, zlyhajú. Keďže syntax podporuje alternatívne vzory v definíciách funkcií, môžeme pokračovať v definícii a rozšíriť ju tak, aby prijímala viac všeobecných argumentov:
Prvé n je tu vzor jedinej premennej, ktorý zodpovedá úplne ľubovoľnému argumentu a viaže ho na meno n, ktoré sa použije vo zvyšku definície. V Haskelli (na rozdiel aspoň od Hope) sa vzory skúšajú v poradí, takže prvá definícia stále platí vo veľmi špecifickom prípade, keď je vstupom 0, zatiaľ čo pre akýkoľvek iný argument funkcia vráti n * f (n-1), pričom n je argument.
Zástupný vzor (často písaný ako _) je tiež jednoduchý: podobne ako názov premennej zodpovedá akejkoľvek hodnote, ale neviaže hodnotu na žiadny názov.
Z primitívnych vzorov z predchádzajúcej časti možno vytvoriť zložitejšie vzory, zvyčajne rovnakým spôsobom, ako sa vytvárajú hodnoty kombináciou iných hodnôt. Rozdiel je potom v tom, že pri premenných a zástupných častiach sa vzor nevytvára do jednej hodnoty, ale zodpovedá skupine hodnôt, ktoré sú kombináciou konkrétnych prvkov a prvkov, ktoré sa môžu v rámci štruktúry vzoru meniť.
Vzor stromu opisuje časť stromu tak, že začína uzlom a špecifikuje niektoré vetvy a uzly a niektoré ponecháva nešpecifikované pomocou premennej alebo zástupného vzoru. Môže pomôcť predstava abstraktného syntaktického stromu programovacieho jazyka a algebraických dátových typov.
V jazyku Haskell definuje nasledujúci riadok algebraický dátový typ Color, ktorý má jediný dátový konštruktor ColorConstructor, ktorý obsahuje celé číslo a reťazec.
Konštruktor je uzol v strome a celé číslo a reťazec sú listy vo vetvách.
Keď chceme napísať funkcie, aby sa farba stala abstraktným dátovým typom, chceme napísať funkcie na rozhranie s dátovým typom, a teda chceme z dátového typu získať niektoré údaje, napríklad len reťazec alebo len celočíselnú časť farby.
Ak odovzdáme premennú typu Color, ako môžeme z tejto premennej získať údaje? Napríklad pre funkciu na získanie celočíselnej časti premennej Color môžeme použiť jednoduchý stromový vzor a napísať:
Filtrovanie údajov pomocou vzorov
Na filtrovanie údajov určitej štruktúry možno použiť porovnávanie vzorov. Napríklad v jazyku Haskell sa na tento druh filtrovania môže použiť porozumenie zoznamu:
Porovnávanie vzorov v systéme Mathematica
V systéme Mathematica existuje iba strom, ktorý je vyplnený symbolmi. V doteraz používanej syntaxi jazyka Haskell by sa dala definovať takto
Príklad stromu by potom mohol vyzerať takto
V tradičnej, vhodnejšej syntaxi sa symboly zapisujú tak, ako sú, a úrovne stromu sa reprezentujú pomocou [], takže napríklad a[b,c] je strom s a ako rodičom a b a c ako deťmi.
Vzor v systéme Mathematica spočíva v umiestnení znakov „_“ na pozície v tomto strome. Napríklad vzor
Zodpovedá prvkom ako A, A alebo všeobecnejšie A[x], kde x je ľubovoľná entita. V tomto prípade je A konkrétny prvok, zatiaľ čo _ označuje časť stromu, ktorú možno meniť. Symbol pripojený k _ viaže zhodu na toto meno premennej, zatiaľ čo symbol pripojený k _ obmedzuje zhodu na uzly tohto symbolu.
Funkcia Mathematica Cases filtruje prvky prvého argumentu, ktoré zodpovedajú vzoru v druhom argumente:
Porovnávanie vzorov sa vzťahuje na štruktúru výrazov. V nasledujúcom príklade,
pretože iba tieto prvky budú zodpovedať vyššie uvedenému vzoru a[b[_],_].
V systéme Mathematica je možné extrahovať aj štruktúry, ktoré vznikajú v priebehu výpočtu, bez ohľadu na to, ako a kde sa objavia. Na sledovanie výpočtu a vrátenie prvkov, ktoré sa zhodujú so vzorom, možno použiť funkciu Trace. Napríklad Fibonacciho postupnosť môžeme definovať ako
Potom si môžeme polo it otázku: Dané fib, aká je postupnosť rekurzívnych Fibonacciho volaní?
vráti štruktúru, ktorá predstavuje výskyty vzoru fib[_] vo výpočtovej štruktúre:
V symbolických programovacích jazykoch je jednoduché mať vzory ako argumenty funkcií alebo ako prvky dátových štruktúr. Dôsledkom toho je možnosť používať vzory na deklaratívne vytváranie výrokov o častiach údajov a na flexibilné inštrukcie funkciám, ako majú pracovať.
Na vytvorenie efektívnejších verzií kódu možno použiť napríklad funkciu Compile systému Mathematica. V nasledujúcom príklade na detailoch nijako zvlášť nezáleží; dôležité je, že podvýraz {{com[_], _Integer}} dáva funkcii Compile pokyn, že výrazy v tvare com[_] možno na účely kompilácie považovať za celé čísla:
Takto fungujú aj poštové schránky v Erlangu.
Porovnávanie vzorov a reťazcov
Zďaleka najbežnejšia forma porovnávania vzorov zahŕňa reťazce znakov. V mnohých programovacích jazykoch sa na reprezentáciu regulárnych výrazov, čo sú vzory opisujúce reťazcové znaky, používa osobitná syntax reťazcov.
Je však možné vykonať určité porovnávanie vzorov reťazcov v rámci toho istého rámca, o ktorom sme hovorili v tomto článku.
V systéme Mathematica sú reťazce reprezentované ako stromy koreňa StringExpression a všetkých znakov v poradí ako potomkov koreňa. Preto na porovnanie „ľubovoľného množstva končiacich znakov“ je potrebný nový zástupný znak ___ na rozdiel od znaku _, ktorý by sa zhodoval len s jedným znakom.
V jazyku Haskell a vo funkcionálnych programovacích jazykoch všeobecne sú reťazce reprezentované ako funkcionálne zoznamy znakov. Funkčný zoznam je definovaný ako prázdny zoznam alebo prvok vytvorený na základe existujúceho zoznamu. V syntaxi jazyka Haskell:
Štruktúra pre zoznam s niektorými prvkami je teda element:list. Pri porovnávaní vzorov tvrdíme, že určitý údaj sa rovná určitému vzoru. Napríklad vo funkcii:
tvrdíme, že prvý prvok argumentu head sa volá element a funkcia ho vráti. Vieme, že ide o prvý prvok, pretože podľa spôsobu definovania zoznamov je na zoznam konštruovaný jeden prvok. Tento jediný prvok musí byť prvý. Prázdny zoznam by vôbec nezodpovedal vzoru, pretože prázdny zoznam nemá hlavu (prvý skonštruovaný prvok).
V príklade nemáme žiadne použitie pre zoznam, takže ho môžeme ignorovať, a tak napísať funkciu:
Ekvivalentná transformácia Mathematica je vyjadrená ako
Napríklad v systéme Mathematica,
bude zodpovedať reťazcu, ktorý obsahuje dva znaky a začína písmenom „a“.
Rovnaký vzor v jazyku Haskell:
Symbolické entity možno zaviesť na reprezentáciu mnohých rôznych tried relevantných vlastností reťazca. Napríklad,
bude zodpovedať reťazcu, ktorý sa skladá najprv z písmena a potom z čísla.
Hlavnou výhodou symbolickej manipulácie s reťazcami je, že môže byť úplne integrovaná do zvyšku programovacieho jazyka, a nie ako samostatná, účelová podjednotka. Celú silu jazyka možno využiť na zostavovanie samotných vzorov alebo na analýzu a transformáciu programov, ktoré ich obsahujú.
Táto časť je vsuvkou. Môžete pomôcť tým, že ju doplníte.
Prvé počítačové programy, ktoré používali porovnávanie vzorov, boli textové editory. V Bell Labs rozšíril Ken Thompson funkcie vyhľadávania a nahrádzania editora QED o regulárne výrazy. Medzi prvé programovacie jazyky s konštrukciami na porovnávanie vzorov patria SNOBOL z roku 1962, NPL z roku 1977 a KRC z roku 1981.
Táto časť je vsuvkou. Môžete pomôcť tým, že ju doplníte.