Ich mache Sie auf eine Übersetzung eines wunderbaren frischen Artikels von Justin Le aufmerksam. In seinem Blog in Code spricht dieser Autor in einer recht einfachen Sprache über die mathematische Essenz schöner und eleganter funktionaler Lösungen für praktische Probleme. In diesem Artikel wird im Detail ein Beispiel dafür untersucht, wie die Übertragung der mathematischen Struktur, die Daten in einem Themenbereich bilden, auf ein System von Programmtypen sofort zu einer funktionierenden Lösung führen kann, wie Gerald und Sassman „automatisch“ geschrieben haben.

Der im Bild gezeigte Code ist eine vollwertige, in sich geschlossene, erweiterbare Implementierung des Parsers für reguläre Ausdrücke, der von Grund auf neu geschrieben wurde. Erstklassige, echte Magie!

Heute implementieren wir anwendungsbezogene reguläre Ausdrücke und Parser (im Sinne der Regex-Anwendungsbibliothek ) unter Verwendung freier algebraischer Strukturen! Freie Strukturen sind eines meiner Lieblingswerkzeuge in Haskell, und ich habe früher über freie Gruppen , Variationen zum Thema freie Monaden und den „freien“ Anwendungsfunktor für Monoide geschrieben .

Reguläre Ausdrücke (und Parser für sie) sind in der Programmierung und in der Informatik allgegenwärtig. Ich hoffe, dass ich durch die Demonstration, wie einfach sie mithilfe freier Strukturen zu implementieren sind, dem Leser helfen kann, die Vorzüge dieses Ansatzes zu erkennen, ohne befürchten zu müssen, sich in unnötigen Details zu verlieren.

Der gesamte Code im Artikel ist online als "stapelbare ausführbare Datei" verfügbar . Wenn Sie es ausführen ( ./regexp.hs ), beginnt die GHCi-Sitzung mit allen Definitionen, sodass Sie die Möglichkeit haben, mit Funktionen und ihren Typen herumzuspielen.

Dieser Artikel ist für den "fortgeschrittenen Anfänger" oder den "Anfängerspezialisten" in Haskell vollständig verständlich. Es erfordert Kenntnisse der Grundkonzepte einer Sprache: Mustervergleich, algebraische Datentypen und Abstraktionen wie Monoide, Funktoren und Notationen.

Reguläre Sprachen

Ein regulärer Ausdruck ist eine Möglichkeit, eine reguläre Sprache zu definieren. Formal besteht ein solcher Ausdruck aus drei Grundelementen:

1. Eine leere Menge ist ein Element, das nichts zugeordnet wird.
2. Eine leere Zeichenfolge ist ein neutrales Element, das trivial mit einer leeren Zeichenfolge übereinstimmt.
3. Ein Literal ist ein Symbol, das zu sich selbst passt. Viel von einem Element.

Und auch aus drei Operationen:

1. Verkettung: RS , Folge von Ausdrücken. Das Produkt von Sets (kartesisch).
2. Alternative: R|S , Wahl zwischen Ausdrücken. Die Vereinigung von Mengen.
3. Wedge Star: R* , Wiederholung eines Ausdrucks beliebig oft (einschließlich Null).

Und das ist alles, was reguläre Ausdrücke ausmacht, nicht mehr und nicht weniger. Aus diesen Grundkomponenten können Sie alle anderen bekannten Operationen für reguläre Ausdrücke erstellen. Beispielsweise kann a+ als aa* ausgedrückt werden, und Kategorien wie \w können als Alternative zu geeigneten Zeichen dargestellt werden.

Alternativer Funktor

Wenn Sie sich die Struktur regulärer Ausdrücke ansehen, kommt Ihnen das nicht bekannt vor? Es erinnert mich sehr an die Alternative Typklasse. Wenn ein Funktor zu dieser Klasse gehört, bedeutet dies, dass für diese Klasse Folgendes definiert ist:

1. Ein leeres Element, das einem Fehler oder einem Berechnungsfehler entspricht.
2. pure x - ein einzelnes Element (aus der Applicative Klasse).
3. Operation <*> , Organisation von sequentiellen Berechnungen.
4. Operation <|> , Organisation alternativer Berechnungen.
5. Die Funktion many ist die Operation, bei der Berechnungen null oder mehrmals wiederholt werden.

All dies ist dem Aufbau einer regulären Sprache sehr ähnlich, oder? Vielleicht ist der alternative Funktor fast das, was wir brauchen. Das einzige, was fehlt, ist das Primitiv, das dem wörtlichen Charakter entspricht.

Jeder, der neu in der Alternative Klasse ist, kann eine gute Einführung in Typeclassopedia finden . Im Rahmen unseres Artikels stellt diese Klasse jedoch einfach ein „Doppelmonoid“ mit zwei Kombinationsmöglichkeiten für <*> und <|> , die gewissermaßen mit den Operationen * und + für Zahlen verglichen werden können. Um einen alternativen Funktor zu bestimmen, sind im Allgemeinen die obigen fünf Punkte und einige zusätzliche Gesetze der Kommutativität und Verteilbarkeit ausreichend.

 (<*>) :: Applicative f => f (a -> b) -> fa -> fb 

 (<*) :: Applicative f => fa -> fb -> fa (*>) :: Applicative f => fa -> fb -> fb 

Daher können wir reguläre Ausdrücke als alternativen Funktor sowie als Grundelement für einen wörtlichen Charakter betrachten. Es gibt aber auch eine andere Sichtweise, die uns direkt zu freien Strukturen führt. Anstelle des "alternativen Funktors mit Literalen" können wir das Literal in eine Instanz der Alternative Klasse verwandeln.

Freiheit

Lass uns so schreiben. Typ für primitives Literal:

 data Prim a = Prim Char a deriving Functor 

Da wir mit Funktoren arbeiten (anwendbar, alternativ), wird mit all unseren regulären Ausdrücken ein bestimmtes „Ergebnis“ verknüpft. Dies liegt daran, dass beim Definieren einer Instanz für die Klassen Functor , Applicative und Alternative ein Parametertyp erforderlich ist.

Einerseits können Sie diesen Typ ignorieren, andererseits sollten Sie diesen Wert als Ergebnis der Übereinstimmung mit einem regulären Ausdruck verwenden, wie dies in industriellen Anwendungen der Fall ist, die mit regulären Ausdrücken arbeiten.

In unserem Fall stellt Prim 'a' 1 :: Prim Int ein Primitiv dar, das dem Zeichen 'a' und sofort interpretiert wird, was zu einer Einheit führt.

Nun, jetzt ... geben wir unserem Grundelement die gewünschte mathematische Struktur mit dem kostenlosen alternativen Funktor aus der free Bibliothek:

 import Control.Alternative.Free type RegExp = Alt Prim 

Das ist alles! Dies ist unser vollständiger Typ für reguläre Ausdrücke! Wenn wir den Alt Typ als Instanz der Functor Klasse Functor , haben wir alle Operationen aus den Klassen Applicative und Alternative , da es in diesem Fall Instanzen von Applicative (Alt f) und Alternative (Alt f) . Jetzt haben wir:

• Trivial leerer Satz - empty aus der Alternative Klasse
• Leere Zeichenfolge - pure aus der Applicative
• Wörtlicher Charakter - Basic Prim
• Verkettung - <*> aus der Applicative Klasse
• Alternative - <|> aus der Klasse Alternative
• Kleene Star - many aus der Alternative

Und das alles haben wir völlig "frei" bekommen, das heißt "kostenlos"!

Im Wesentlichen liefert uns eine freie Struktur automatisch nur eine Abstraktion für den Basistyp und nichts weiter. Reguläre Ausdrücke an sich stellen aber auch nur eine Struktur dar: Grundelemente und eine Reihe von Operationen, weder mehr noch weniger, sodass der kostenlose alternative Funktor uns genau das bietet, was wir brauchen. Nicht mehr, aber nicht weniger.

Nach dem Hinzufügen einiger praktischer Wrapper-Funktionen ... ist die Arbeit am Typ abgeschlossen!

 -- | charAs:   ,    charAs :: Char -> a -> RegExp a charAs cx = liftAlt (Prim cx) -- liftAlt :: fa -> Alt fa   --   Prim   RegExp -- | char:         char :: Char -> RegExp Char char c = charAs cc -- | string:         string :: String -> RegExp String string = traverse char -- , ? 

Beispiele

Nun, lass es uns versuchen. Konstruieren wir den Ausdruck (a|b)(cd)*e , der im Falle einer erfolgreichen Übereinstimmung den Einheitentyp () zurückgibt:

 testRegExp_ :: RegExp () testRegExp_ = void $ (char 'a' <|> char 'b') *> many (string "cd") *> char 'e' 

Die Funktion void :: Functor f => fa -> f () aus dem Data.Functor Paket verwirft das Ergebnis, wir verwenden es, da wir nur am Erfolg des Vergleichs interessiert sind. Die Operatoren <|> , *> und many werden von uns jedoch genau so verwendet, wie es bei der Verkettung oder Auswahl einer der Optionen angenommen wird.

Hier ist ein interessantes, komplizierteres Beispiel. Definieren wir denselben regulären Ausdruck. Jetzt berechnen wir als Ergebnis des Abgleichs die Anzahl der Wiederholungen der Teilstring- cd .

 testRegExp :: RegExp Int testRegExp = (char 'a' <|> char 'b') *> (length <$> many (string "cd")) <* char 'e' 

Die Bedienung der Operatoren *> und <* subtil: Die Pfeile geben das Ergebnis an, das gespeichert werden soll. Und da many (string "cd") :: RegExp [String] eine Liste sich wiederholender Elemente zurückgibt, können wir die Länge dieser Liste berechnen, indem wir die Anzahl der Wiederholungen ermitteln.

Darüber hinaus können -XApplicativeDo mit der Compiler- -XApplicativeDo GHC -XApplicativeDo unseren Ausdruck in do-Notation schreiben, was wahrscheinlich einfacher zu verstehen ist:

 testRegExpDo :: RegExp Int testRegExpDo = do char 'a' <|> char 'b' cds <- many (string "cd") char 'e' pure (length cds) 

Dies alles ähnelt in gewisser Weise der Art und Weise, wie wir das Ergebnis des Parsens eines Strings mithilfe eines regulären Ausdrucks „erfassen“ und Zugriff darauf erhalten. Hier ist ein Beispiel in Ruby:

 irb> /(a|b)((cd)*)e/.match("acdcdcdcde")[2] => "cdcdcdcd" 

Der einzige Unterschied besteht darin, dass wir eine Nachbearbeitung hinzugefügt haben, um die Anzahl der Wiederholungen zu berechnen.

Hier ist ein weiteres praktisches reguläres \d , das einer Zahl von 0 bis 9 entspricht und eine Zahl zurückgibt:

 digit :: RegExp Int digit = asum [ charAs (intToDigit i) i | i <- [0..9] ] 

Hier stellt die asum Funktion aus dem Control.Applicative.Alternative Paket eine Auswahl aus den Listenelementen asum [x,y,z] = x <|> y <|> z , und die intToDigit Funktion intToDigit im Data.Char Paket definiert. Und wieder können wir ziemlich elegante Dinge erstellen, zum Beispiel den Ausdruck \[\d\] , der der Zahl in eckigen Klammern entspricht:

 bracketDigit :: RegExp Int bracketDigit = char '[' *> digit <* char ']' 

Parsen

Wir haben lediglich den Datentyp für ein Literal mit Verkettung, Auswahl und Wiederholung beschrieben. Großartig! Aber was wir wirklich brauchen, ist eine Zeichenfolge mit einem regulären Ausdruck abzugleichen, oder? Wie kann uns ein kostenloser alternativer Funktor dabei helfen? In der Tat wird es viel helfen. Schauen wir uns zwei Möglichkeiten an, um dies zu tun!

Entladen Sie den alternativen Funktor

Was ist Freiheit?

Die kanonische Art, eine freie Struktur zu verwenden, besteht darin, sie unter Verwendung einer geeigneten Algebra zu einer konkreten Struktur zu falten. Beispielsweise wandelt die foldMap Transformation ein freies Monoid (Liste) in den Wert einer beliebigen Instanz der Monoid Klasse um:

 foldMap :: Monoid m => (a -> m) -> ([a] -> m) 

Die Funktion foldMap wandelt die Transformation a -> m in die Transformation [a] -> m (oder FreeMonoid a -> m ) mit einem bestimmten Monoid m . Die allgemeine Idee ist, dass Sie durch die Verwendung einer freien Struktur ihre spezifische Verwendung "für später" verschieben können, wobei der Zeitpunkt der Erstellung und der Zeitpunkt der Verwendung der Struktur getrennt werden.

Zum Beispiel können wir ein freies Monoid aus Zahlen konstruieren:

 -- |  "" `Int`     `Int`,  `liftAlt`. liftFM :: Int -> [Int] liftFM x = [x] myMon :: [Int] myMon = liftFM 1 <> liftFM 2 <> liftFM 3 <> liftFM 4 

Und jetzt können wir entscheiden, wie wir die Operation <> interpretieren wollen:
Vielleicht dieser Zusatz?

 ghci> foldMap Sum myMon Sum 10 -- 1 + 2 + 3 + 4 

Oder Multiplikation?

 ghci> foldMap Product myMon Product 24 -- 1 * 2 * 3 * 4 

Oder vielleicht die Berechnung der maximalen Anzahl?

 ghci> foldMap Max myMon Max 4 -- 1 `max` 2 `max` 3 `max` 4 

Die Idee ist, die Auswahl eines bestimmten Monoids zu verschieben, indem zuerst eine freie Sammlung der Nummern 1, 2, 3 und 4 erstellt wird. Ein freies Monoid über Zahlen bestimmt die Struktur darüber, die Sie benötigen, nicht mehr und nicht weniger. Um foldMap wir an, wie der Basistyp wahrgenommen werden soll, indem der Operator <> an ein bestimmtes Monoid übergeben wird.

Interpretation in einem State Functor

In der Praxis besteht das Erhalten eines Ergebnisses aus einer freien Struktur darin, einen geeigneten Funktor zu finden (oder zu erstellen), der uns das gewünschte Verhalten liefert. In unserem Fall haben wir das Glück, dass es eine bestimmte Implementierung der Alternative Klasse gibt, die genau so funktioniert, wie wir sie benötigen: StateT String Maybe .

Das Produkt <*> für diesen Funktor besteht darin, eine Folge von Zustandsänderungen zu organisieren. In unserem Fall betrachten wir unter dem Status den Rest der analysierten Zeichenfolge, sodass die sequentielle Analyse die beste Übereinstimmung für die Operation <*> .

Und seine Summe <|> funktioniert wie Backtracking, eine Suche mit einer Rückkehr zur Alternative im Fehlerfall. Es speichert den Status seit der letzten erfolgreichen Ausführung der Analyse und kehrt zu ihm zurück, wenn die Alternative nicht erfolgreich ist. Dies ist genau das Verhalten, das wir vom Ausdruck R|S erwarten R|S

Schließlich heißt eine natürliche Transformation für einen kostenlosen alternativen Funktor runAlt :

 runAlt :: Alternative f => (forall b. pb -> fb) -> Alt pa -> fa 

Oder für den Typ RegExp:

 runAlt :: Alternative f => (forall b. Prim b -> fb) -> RegExp a -> fa 

Wenn Sie mit RankN Typen (mit forall b. Construction) nicht vertraut sind, finden Sie hier eine gute Einführung. Der Punkt hier ist, dass Sie eine runAlt Funktion runAlt müssen, die mit Prim b für absolut jedes b funktioniert und nicht für einen bestimmten Typ, wie beispielsweise Int und Bool . Das heißt, wie bei foldMap wir nur angeben, was mit dem Basistyp foldMap . Beantworten Sie in unserem Fall die Frage: "Was ist mit dem Typ Prim zu tun?"

 processPrim :: Prim a -> StateT String Maybe a processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

Dies ist eine Interpretation von Prim als Aktion im Kontext der StateT String Maybe Zeichenfolge. StateT String Maybe ist der Status eine StateT String Maybe Zeichenfolge. Ich möchte Sie daran erinnern, dass Prim Informationen über das übereinstimmende Zeichen c und seine Interpretation in Form eines Wertes von x . Prim Verarbeitung besteht aus den folgenden Schritten:

• Mit get Status (noch nicht analysierter Teil der Zeichenfolge) und drucken sofort das erste Zeichen und den Rest aus. Wenn die Zeile leer ist, wird eine Alternative zurückgegeben. ( Der StateT Transformator wirkt innerhalb des Vielleicht-Funktors. Wenn es nicht möglich ist, das Muster auf der rechten Seite des Operators <- innerhalb des do-Blocks StateT , enden die Berechnungen mit dem empty Ergebnis, dh Nothing . Ca. Trans. ).
• Wir verwenden den Schutzausdruck, um das aktuelle Zeichen mit dem angegebenen Zeichen abzugleichen. Im Fehlerfall wird empty zurückgegeben und wir gehen zur alternativen Option über.
• Wir ändern den Status, indem wir die analysierte Zeichenfolge durch ihren "Schwanz" ersetzen, da zu diesem Zeitpunkt das aktuelle Zeichen bereits als erfolgreich analysiert betrachtet werden kann.
• Wir geben zurück, was das Prim Primitiv zurückgeben soll.

Mit dieser Funktion können Sie RegEx bereits einem Zeichenfolgenpräfix zuordnen. Dazu müssen Sie die Berechnungen mit runAlt und runStateT runAlt und die analysierte Zeichenfolge als Argument an die letzte Funktion übergeben:

 matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) 

Das ist alles! Mal sehen, wie unsere erste Lösung funktioniert:

 ghci> matchPrefix testRegexp_ "acdcdcde" Just () ghci> matchPrefix testRegexp_ "acdcdcdx" Nothing ghci> matchPrefix testRegexp "acdcdcde" Just 3 ghci> matchPrefix testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchPrefix digit "9" Just 9 ghci> matchPrefix bracketDigit "[2]" Just 2 ghci> matchPrefix (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchPrefix (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

Warten Sie, was war das?

Es scheint, dass alles etwas schneller ging als erwartet. Vor einer Minute haben wir unser Primitiv geschrieben und dann wieder! und der funktionierende Parser ist bereit. Hier in der Tat der gesamte Schlüsselcode, ein paar Zeilen in Haskell:

 import Control.Monad.Trans.State (evalStateT, put, get) import Control.Alternative.Free (runAlt, Alt) import Control.Applicative import Control.Monad (guard) data Prim a = Prim Char a deriving Functor type RegExp = Alt Prim matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) where processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

Und haben wir einen voll funktionsfähigen Parser für reguläre Ausdrücke? Was ist passiert?

Denken Sie daran, dass Alt Prim auf einer hohen Abstraktionsebene bereits pure , empty Prim , <*> , <|> und many in seiner Struktur enthält (es gibt eine unangenehme Subtilität bei diesem Operator, aber dazu später mehr). Was runAlt tut, ist das Verhalten eines bestimmten alternativen Funktors (in unserem Fall StateT String Maybe ), um das Verhalten der pure , empty , <*> , <|> und many Operatoren zu steuern. StateT verfügt jedoch nicht über einen integrierten Operator, der Prim ähnelt, und dafür mussten wir StateT schreiben.

Für den Prim Typ verwendet die Funktion runAlt , und für pure , empty , <*> , <|> und many wird eine geeignete Instanz der Alternative Klasse verwendet. Somit werden 83% der Arbeit vom StateT Funktor für uns StateT , und die restlichen 17% werden von StateT erledigt. In Wahrheit ist das etwas enttäuschend. Man könnte fragen: Warum war es überhaupt notwendig, mit dem Alt Wrapper zu beginnen? Warum nicht sofort den Typ RegExp = StateT String Maybe und das entsprechende char :: Char -> StateT String Maybe Char ? Wenn alles im StateT- StateT erledigt ist, warum sollte man sich dann mit Alt - einem kostenlosen alternativen Funktor?

Alt Hauptvorteil von Alt gegenüber StateT ist, dass StateT ... ein ziemlich mächtiges Werkzeug ist. Tatsächlich ist er jedoch bis zur Absurdität mächtig. Es kann verwendet werden, um eine große Anzahl der unterschiedlichsten Berechnungen und Strukturen darzustellen, und es ist unangenehm, sich etwas vorzustellen, das kein regulärer Ausdruck ist. Nehmen wir an, etwas Grundlegendes wie put "hello" :: StateT String Maybe () stimmt mit keinem gültigen regulären Ausdruck überein, ist jedoch vom gleichen Typ wie RegExp () . Während wir also sagen, dass Alt Prim mit einem regulären Ausdruck übereinstimmt, nicht mehr, aber nicht weniger, können wir mit StateT String Maybe nicht dasselbe sagen. Der Alt Prim Typ ist die perfekte Darstellung eines regulären Ausdrucks. Alles, was mit seiner Hilfe ausgedrückt werden kann, ist ein regulärer Ausdruck, aber alles, was nicht so ein Ausdruck ist, kann nicht mit seiner Hilfe ausgedrückt werden. Hier gibt es jedoch auch einige unangenehme Feinheiten, die mit Haskells Faulheit verbunden sind, dazu später mehr.

Hier können wir StateT nur als einen Kontext betrachten, der für einen verwendet wird
Interpretationen regulärer Ausdrücke - als Parser. Sie können sich aber auch andere Möglichkeiten vorstellen, RegExp zu verwenden. Zum Beispiel benötigen wir möglicherweise eine Textdarstellung, die StateT nicht zulässt.

Wir können nicht sagen, dass StateT String Maybe ein regulärer Ausdruck ist, nur dass dieser Funktor einen Parser darstellen kann, der auf regulären Grammatiken basiert. Aber über Alt Prim wir mit Sicherheit sagen, dass dies ein regulärer Ausdruck ist ( wie Mathematiker sagen, sind sie bis zum Isomorphismus gleich, ca. Trans. ).

Direkte Nutzung der freien Struktur

All dies ist natürlich sehr gut, aber was ist, wenn wir 83% der Arbeit nicht auf Code für einen Typ verlagern möchten, der von jemandem für uns geschrieben wurde? Ist es möglich, die freie Alt Struktur direkt zum Schreiben eines Parsers zu verwenden? Diese Frage ähnelt der folgenden: Wie schreibe foldMap eine Funktion, die Listen verarbeitet (durch Abgleichen der Konstruktoren (:) und [] ), anstatt nur foldMap ? Wie kann man direkt mit dieser Struktur arbeiten, anstatt die Arbeit an ein bestimmtes Monoid zu delegieren?

Schön, dass du gefragt hast! Werfen wir einen Blick auf die Definition eines kostenlosen alternativen Funktors:

 newtype Alt fa = Alt { alternatives :: [AltF fa] } data AltF fa = forall r. Ap (fr) (Alt f (r -> a)) | Pure a 

Dies ist ein ungewöhnlicher Typ, der durch gegenseitige Rekursion definiert wird, sodass er sehr verwirrend aussehen kann. Eine Möglichkeit, dies zu verstehen, besteht darin, sich vorzustellen, dass Alt xs eine Kette von Alternativen enthält, die mit dem Operator <|> . AltF , f , <*> ( ).

AltF fa [fr] , r . Ap (:) , fr , Pure — [] . forall r. -XExistentialQuantification .

, Alt f , . , ( ) <*> <|> , , [a] <> .

, RegExp a -> String -> Maybe a , , . : .

, Alt . , , .

 matchAlts :: RegExp a -> String -> Maybe a matchAlts (Alt res) xs = asum [ matchChain re xs | re <- res ] 

asum :: [Maybe a] -> Maybe a , Just . ( , Maybe a Alternative — Nothing , <|> . . . )

. AltF , Ap Pure :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = _ matchChain (Pure x) cs = _ 

" ": GHC "", , , . ( Haskell "" (holes) , _ , . . . ) :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = case cs of [] -> Nothing d:ds | c == d -> matchAlts (($ x) <$> next) ds | otherwise -> Nothing matchChain (Pure x) _ = Just x 

Ap ( (:) ), , - . , . Prim r , , next :: RegExp (r -> a) . , next . , "" , Nothing . , Pure x ( [] ), , , .

, , . , , " " Ap , Pure , AltF .., .

:

 ghci> matchAlts testRegexp_ "acdcdcde" Just () ghci> matchAlts testRegexp_ "acdcdcdx" Nothing ghci> matchAlts testRegexp "acdcdcde" Just 3 ghci> matchAlts testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchAlts digit "9" Just 9 ghci> matchAlts bracketDigit "[2]" Just 2 ghci> matchAlts (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchAlts (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

?

foldMap . , , foldMap, , , , ! , — , — (:) [] .

, , : , , , (:) , [] . , . , [1,2,3] <> [4] , [1] <> [2,3] <> [4] . , , .

. , :

 data RegExp a = Empty | Pure a | Prim Char a | forall r. Seq (RegExp r) (RegExp (r -> a)) | Union (RegExp a) (RegExp a) | Many (RegExp a) 

RegExp , . . , RegExp :

 -- | a|(b|c) abc1 :: RegExp Int abc1 = Prim 'a' 1 `Union` (Prim 'b' 2 `Union` Prim 'c' 3) -- | (a|b)|c abc2 :: RegExp Int abc2 = (Prim 'a' 1 `Union` Prim 'b' 2) `Union` Prim 'c' 3 

, .

Alt Prim , , , . , matchAlts , . (a|b)|c a|(b|c) . Alt . , , .

, , (a|b)|c , (a|b)|c , , , RegExp . Alt , .

, , Alt , Alt Prim . , Alt Prim a|a a . , Alt f f . , : . , , , .

, . , , . RegExp , , — .

, Haskell. , - [a] . ( , - , "" $$$\bot$, - "" . ca. . )

: a|aa|aaa|aaaa|aaaaa|aaaaaa|... , ( , , , . . . ). , Haskell . , Alt many . , a* a|aa|aaa|aaaa|aaaaa|aaaaaa|... , . - many (char 'a') , . Haskell Alt , .

, , , , (), . , many .

, ! "" Alt , Control.Alternative.Free.Final , many (, , ).

, , runAlt . , Alternative , many ( RE regex-applicative ) . , Haskell , , , many .

, . ( ), ( , , . . ). matchPrefix , , , . , , , , . , GHC .

, , tails ( ) mapMaybe ( ). , , listToMaybe .

 matches :: RegExp a -> String -> [a] matches re = mapMaybe (matchPrefix re) . tails firstMatch :: RegExp a -> String -> Maybe a firstMatch re = listToMaybe . matches re 

, , matchPrefix Nothing , listToMaybe , Nothing ( , . . . ).

, . , , — , . , . , , , .

Alt Prim , : , , , .

? . :

 data Prim a = Only Char a --    | Letter a --     | Digit (Int -> a) --    , | Wildcard (Char -> a) --    , | Satisfy (Char -> Maybe a) --    , --   

, . .

, , . runAlt Alt .

(). , , , , . | . ( , . . . ). , - . , MonadPlus - , , . , .

, , . , !