Haskell Parser Combinator - do Notation

Question

ich einen Parser combinator Bibliothek ein Tutorial zu lesen in Bezug auf den Aufbau und stieß ich auf ein Verfahren, das verstehe ich nicht ganz.

newtype Parser a = Parser {parse :: String -> [(a,String)]} 

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a 
chainl p op a = (p `chainl1` op) <|> return a 

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a 
p `chainl1` op = do {a <- p; rest a} 
    where rest a = (do f <- op 
        b <- p 
        rest (f a b)) 
       <|> return a 

bind :: Parser a -> (a -> Parser b) -> Parser b 
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s 

die bind ist die Umsetzung des (>>=) Betreiber. Ich verstehe nicht ganz, wie die chainl1 Funktion funktioniert. Von dem, was ich kann Ihnen f von op extrahieren und dann sehen, wenden Sie es auf f a b und Sie Rekursion, aber ich nicht bekommen, wie Sie eine Funktion aus dem Parser extrahieren, wenn sie eine Liste von Tupeln zurückgeben sollte?

Answer 1

Start bei der Definition von Parser, indem man:

newtype Parser a = Parser {parse :: String -> [(a,String)]}` 

A Parser a ist wirklich nur ein Wrapper um eine Funktion (die wir später mit parse laufen können), die ein String und gibt eine Liste von Paaren nimmt, wobei jedes Paar einen a enthält, der bei der Verarbeitung der Zeichenfolge gefunden wurde, zusammen mit dem Rest der Zeichenfolge, die noch verarbeitet werden muss.

Nun ein Blick auf den Teil des Codes in chainl1, die Sie ist verwirrend: den Teil, wo Sie f aus op extrahieren:

f <- op 

Sie bemerkt: „Ich weiß nicht bekommen, wie Sie eine Funktion aus dem Parser extrahieren wenn es eine Liste von Tupeln zurückgeben soll. "

Es ist wahr, dass, wenn wir ein Parser a mit einer Schnur laufen (mit parse), haben wir eine Liste vom Typ [(a,String)] als Ergebnis erhalten. Aber dieser Code sagt nicht parse op s. Stattdessen verwenden wir hier bind (mit der Do-Notation syntaktischen Zucker). Das Problem ist, dass Sie über die Definition des Parser Datatyps nachdenken, aber Sie denken nicht viel darüber nach, was bind speziell tut.

Schauen wir uns an, was bind in der Parser Monade ein bisschen vorsichtiger macht.

bind :: Parser a -> (a -> Parser b) -> Parser b 
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s 

Was macht p >>= f? Es gibt eine Parser, die, wenn eine Zeichenfolge s gegeben wird, Folgendes: Zuerst läuft Parser p mit der zu analysierenden Zeichenfolge, s. Dies ergibt, wie Sie richtig angemerkt haben, eine Liste des Typs [(a, String)]: d. H. Eine Liste der Werte vom Typ a, die angetroffen wurden, zusammen mit der Zeichenkette, die nach dem Auftreten jedes Wertes zurückblieb. Dann nimmt es diese Liste von Paaren und wendet eine Funktion auf jedes Paar an. Insbesondere ist jedes Paar (a, s') in dieser Liste transformiert durch (1) f an den geparsten Wert Anwenden a (f a gibt einen neuen Parser), und dann (2) Diesen neuen Parser mit den verbleibenden Laufe s' Zeichenfolge. Dies ist eine Funktion von einem Tupel zu einer Liste von Tupeln: (a, s') -> [(b, s'')] ... und da wir durch parse p s jedes Tupel diese Funktion über in der ursprünglichen Liste zurück kartieren, diese enden uns eine Liste von Listen von Tupeln geben: [[(b, s'')]]. Also verketten (oder verbinden) wir diese Liste in eine einzige Liste [(b, s'')]. Alles in allem haben wir dann eine Funktion von s bis [(b, s'')], die wir dann in einen Parser Newtype einpacken.

Der entscheidende Punkt ist, dass, wenn wir f <- op sagen, oder op >>= \f -> ..., die den Namen von op analysiert f auf die Werte zuordnet, aber f nicht eine Liste von Tupeln ist, b/c es nicht das Ergebnis ist parse op s laufen.

Im Allgemeinen werden Sie eine Menge von Haskell-Code sehen, dass einige Datentyp SomeMonad a, zusammen mit einem bind Methode definiert, die eine Menge von den schmutzigen Details für Sie versteckt und lässt Sie den Zugriff auf die a Werte erhalten, die Sie interessieren Verwenden Do-Notation wie folgt: a <- ma. Es kann lehrreich sein, die Monade zu sehen, um zu sehen, wie bind Zustand hinter den Kulissen für Sie passiert. Ähnlich verhält es sich hier, wenn Sie Parser kombinieren, interessieren Sie sich am meisten für die Werte, die der Parser erkennen soll ... bind versteckt die ganze schmutzige Arbeit, die die Strings beinhaltet, die beim Erkennen eines Wertes vom Typ a verbleiben.