Wir definieren einen Datentyp fuer regulaere Ausdruecke ueber einem Alphabet a: > data RE a = Lit a > | Alt (RE a) (RE a) > | Conc (RE a) (RE a) > | Star (RE a) Als Beispiel koennen wir z.B. den Ausdruck (a|b|c) definieren: > abc = Alt (Alt (Lit 'a') (Lit 'b')) (Lit 'c') Ein weiteres Beispiel ist der Ausdruck (ab*): > abstar = Conc (Lit 'a') (Star (Lit 'b')) Wir koennen aber auch einfach die Sprache der regulaeren Ausdruecke um weitere Konstrukte erweitern, wie z.B. einen plus-Operator, der eine mindestens einmalige Wiederholung bezeichnet: > plus re = Conc re (Star re) Die Semantik regulaerer Ausdruecke kann direkt durch eine Semantik-Funktion definiert werden, wie man dies auch in der Theorie der regulaeren Ausdruecke macht. Somit wird durch die Semantik jedem regulaeren Ausdruck ein dadurch beschriebenes Wort zugeordnet. Da es mehrere moegliche Worte gibt, beschreiben wir dies durch eine nichtdeterministische Funktion. > sem :: RE a -> [a] > sem (Lit c) = [c] > sem (Alt a b) = sem a ? sem b > sem (Conc a b) = sem a ++ sem b > sem (Star a) = [] ? sem (Conc a (Star a)) Beispielauswertung: sem abc -> "a" oder "b" oder "c" sem abstar -> "a" oder "ab" oder "abb" ... Wenn wir einen String gegen einen regulaeren Ausdruck matchen wollen, koennen wir dies einfach durch folgendes Constraint beschreiben: > match :: RE a -> [a] -> Success > match r s = sem r =:= s Ein Constraint, das aehnlich wie Unix's grep feststellt, ob ein regulaerer Ausdruck irgendwo in einem String enthalten ist, koennen wir wie folgt definieren: > grep :: RE a -> [a] -> Success > grep r s = xs ++ sem r ++ ys =:= s where xs,ys free Beispielauswertungen: grep abc "dbe" grep abstar "dabe" Beachte, dass der letzte Ausdruck eine endliche Auswertung hat, obwohl es unendliche viele Woerter gibt, zu denen abstar auswerten kann. Wir koennen grep auch so erweitern, dass wir als Ergebnis den String ausgeben, ab dem der regulaere Ausdruck passt: > grepShow :: RE a -> [a] -> [a] > grepShow r s | xs ++ sem r ++ ys =:= s = drop (length xs) s > where xs,ys free Beispielauswertungen: grepShow abstar "dabe" grepShow abc "dbeaxce"