Haskell syntaktický analyzátor - do notácie - haskell, parser-combinators, do-notation

Čítal som návod na zostavenie knižnice kombinátora syntaktického analyzátora a narazil som na metódu, ktorej úplne nerozumiem.

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

na bind je implementácia (>>=) operátor. Nemám dosť pochopiť, ako chainl1 funkčné práce. Z toho, čo ťa vidím, extrahujem f z op a potom to aplikujete na f a b a opakujete, nechápem však, ako extrahujete funkciu z syntaktického analyzátora, keď má vrátiť zoznam n-tíc?

odpovede:

Začnite tým, že sa pozriete na definíciu pojmu Parser:

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

A Parser a je naozaj iba obal okolo funkcie (s ktorou môžeme bežať neskôr) parse), ktoré trvá a String a vráti zoznam párov, kde každý pár obsahuje znak a pri spracovaní reťazca spolu so zvyškom reťazca, ktorý zostáva spracovávať.

Teraz sa pozrite na časť kódu v jazyku chainl1 to je pre vás mätúce: časť, z ktorej vyberiete f z op:

f <- op

Poznamenali ste: „Nerozumiem tomu, ako extrahujete funkciu z analyzátora, keď má vrátiť zoznam n-tíc.“

Je pravda, že keď sme beh a Parser a s reťazcom (pomocou parse), dostaneme zoznam typov [(a,String)] ako výsledok. Tento kód však nehovorí parse op s, Skôr používame bind tu (s nototickým syntaktickým cukrom). Problém je v tom, že uvažujete o vymedzení pojmu Parser typ údajov, ale o čom príliš nerozmýšľate bind konkrétne.

Pozrime sa na čo bind robí v Parser monad trochu opatrnejšie.

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

Čo robí p >>= f robiť? Vracia a Parser to, keď dostane reťazec s, robí nasledujúce: Najprv to beží parser p s reťazcom, ktorý sa má analyzovať, s, Ako ste správne poznamenali, vráti sa zoznam typov [(a, String)]: t. j. zoznam hodnôt typu a narazil, spolu s reťazcom, ktorý zostal po stretnutí s každou hodnotou. Potom vezme tento zoznam párov a použije funkciu na každý pár. Konkrétne každý (a, s") pár v tomto zozname sa transformuje aplikáciou (1) f na analyzovanú hodnotu a (f a vráti nový syntaktický analyzátor) a potom (2) beh tento nový syntaktický analyzátor so zvyšným reťazcom s", Toto je funkcia od n-tice po zoznam n-tíc: (a, s") -> [(b, s"")]... a keďže túto funkciu mapujeme na každé n-tice v pôvodnom zozname vrátené používateľom parse p s, to nám nakoniec poskytne zoznam zoznamov n-tíc: [[(b, s"")]], Tento zoznam teda spojíme (alebo sa pripojíme) do jedného zoznamu [(b, s"")], Celkovo teda máme funkciu s na [(b, s"")], ktoré potom zabalíme do a Parser Newtype.

Kľúčovým bodom je, že keď hovoríme f <- op, alebo op >>= f -> ... ktorý priradí meno f na hodnoty analyzované pomocou op, ale f nie je zoznam n-tíc, b / c nie je výsledkom behu parse op s.

Vo všeobecnosti uvidíte veľa kódu Haskell, ktorý definuje nejaký typ údajov SomeMonad a, spolu s bind metóda, ktorá pre vás skrýva veľa špinavých detailov a umožňuje vám prístup k internetu a hodnoty, na ktorých vám záleží pri používaní notácie: a <- ma, Môže byť poučné pozrieť sa na State a monad vidieť, ako na to bind prechádza okolo štátu za scénami. Podobne aj tu, keď kombinujete analyzátory, vám najviac záleží na hodnotách, ktoré má syntaktický analyzátor rozpoznať ... bind skrýva všetku špinavú prácu, ktorá zahŕňa reťazce, ktoré zostanú po rozpoznaní hodnoty typu a.