Mønster matching

Mønstermatching (engelsk for mønstermatching ) eller mønsterbasert søk er et begrep for prosesseringsprosedyrer for symboler basert på et forhåndsbestemt mønster, søkemasken , diskret identifiserer en diskret struktur eller strukturerer undergrupper.

Mønstertilpasning er for eksempel en metode for fylogenetisk analyse i bioinformatikk .

Grunnleggende

En diskret struktur består av diskrete elementer ( symboler ) og forholdet mellom dem. Eksempler er strenger , men også trær eller grafer . Selve søkemønsteret er også en diskret struktur, men den kan beskrive en hel klasse strukturer ved å bruke flere metategn . I motsetning til mønstergjenkjenning , som tolker kontinuerlige strukturer, fungerer mønstermatching fra starten av en symbolsk representasjon.

Mønstermatching spiller ikke bare en sentral rolle i søket, men også i mønsteret og regelbasert transformasjon av diskrete strukturer. I erstatnings- eller transformasjonssystemer er mønstermatching det første trinnet. Deler av mønsteret er identifisert med deler av den analyserte strukturen. Understrukturene som blir funnet blir deretter brukt som parametere i transformasjonsfunksjonen. Eksempler på slike transformasjoner er tekstutskifting til tegnstrenger og grafutskiftningssystemer .

bruksområder

programmering

I noen funksjonelle eller logiske programmeringsspråk brukes mønstermatching til å behandle data basert på strukturen (f.eks. Scala , Objective CAML , ML , Haskell , Erlang , Opal )

Eksempel på forskjell: En mulig definisjon av det niende Fibonacci-tallet er:

${\ displaystyle {\ text {fib}} (n) = {\ begin {cases} 0 og {\ text {if}} n = 0 \\ 1 & {\ text {if}} n = 1 \\ {\ tekst {fib}} (n-1) + {\ text {fib}} (n-2) og {\ text {ellers}} \ slutt {cases}}}$

Denne definisjonen kan overføres direkte til Haskell ved hjelp av mønstermatching .

-- Matcht die ersten beiden Fälle
fib 0 = 0
fib 1 = 1
-- Alle anderen Zahlen n sind definiert als
fib n = fib(n-1) + fib(n-2)

Eksempel: I Haskell matches argumentene i en funksjonsdefinisjon med mønstre. Et mønster kan, men trenger ikke å være en elementær verdi (f.eks. 0), som i forrige eksempel, men kan også beskrive en datakonstruktør.

-- matcht die leere Liste (Konstruktor [])
f [] = ...
-- matcht alle Listen der Länge > 0 (Konstruktor :), wobei x den Kopf und xs den Listenrest enthält
f (x:xs) = ...

Tekstbehandling

Mønstermatching brukes også til å manipulere tekst. I programmeringsspråk som Perl eller awk og i de fleste tekstredigerere er det verktøy for å søke i en tekst etter et mønster. Mønstrene består av regulære uttrykk .

Se også

litteratur

Simon Peyton Jones (red.): Haskell 98 Språk og biblioteker: Den reviderte rapporten . Cambridge University Press, 2003, ISBN 0-521-82614-4 ( HTML-versjon - Seksjon 3.17, HTML-versjon ).
Richard Bird: Introduksjon til funksjonell programmering ved hjelp av Haskell . 2. utgave. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 .

Languages