Kombinator parsera Haskella - do notacji - haskell, parser-kombinatory, do-notacji

Czytałem samouczek dotyczący budowania biblioteki kombinatora parserów i natknąłem się na metodę, której nie do końca rozumiem.

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

temu bind jest realizacja (>>=) operator. Nie bardzo rozumiem jak chainl1 funkcja działa. Z tego, co widzę, wyciągasz f od op a następnie zastosujesz to do f a b i powracasz, jednak nie rozumiem, jak wyodrębnić funkcję z parsera, kiedy powinna zwrócić listę krotek?

Odpowiedzi:

Zacznij od spojrzenia na definicję Parser:

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

ZA Parser a to tak naprawdę tylko opakowanie funkcji (z którą możemy później uruchomić parse), który wymaga String i zwraca listę par, gdzie każda para zawiera a napotkano podczas przetwarzania ciągu wraz z resztą ciągu, który pozostaje do przetworzenia.

Teraz spójrz na część kodu w chainl1 to cię myli: część, z której wydobywasz f od op:

f <- op

Zauważyłeś: „Nie rozumiem, jak wyodrębnić funkcję z parsera, kiedy powinna zwrócić listę krotek”.

To prawda, że ​​kiedy my biegać za Parser a z ciągiem znaków (używając parse), otrzymujemy listę typów [(a,String)] w rezultacie. Ale ten kod nie mówi parse op s. Raczej używamy bind tutaj (z cukrem syntaktycznym do notacji). Problem polega na tym, że myślisz o definicji Parser typ danych, ale nie zastanawiasz się nad czym bind konkretnie robi.

Spójrzmy na co bind robi w Parser monada trochę ostrożniej.

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

Co robi p >>= f robić? Zwraca a Parser że po podaniu łańcucha s, wykonuje następujące czynności: po pierwsze działa parser p z analizowanym ciągiem, s. To, jak słusznie zauważyłeś, zwraca listę typów [(a, String)]: tj. lista wartości typu a napotkano wraz z łańcuchem pozostałym po napotkaniu każdej wartości. Następnie bierze tę listę par i stosuje funkcję do każdej pary. W szczególności każdy (a, s") Para na tej liście jest przekształcana przez zastosowanie (1) f do przeanalizowanej wartości a (f a zwraca nowy parser), a następnie (2) bieganie ten nowy parser z pozostałym ciągiem s". Jest to funkcja od krotki do listy krotek: (a, s") -> [(b, s"")]... a ponieważ mapujemy tę funkcję na każdą krotkę z oryginalnej listy zwróconej przez parse p s, to daje nam listę list krotek: [[(b, s"")]]. Więc łączymy (lub łączymy) tę listę w jedną listę [(b, s"")]. Podsumowując, mamy funkcję od s do [(b, s"")], które następnie zawijamy w Parser nowy typ.

Najważniejsze jest to, że kiedy mówimy f <- op, lub op >>= f -> ... która przypisuje nazwę f do wartości przeanalizowanych przez op, ale f nie jest listą krotek, b / c nie jest wynikiem działania parse op s.

Ogólnie rzecz biorąc, zobaczysz dużo kodu Haskell, który definiuje jakiś typ danych SomeMonad a, wraz z bind Metoda, która ukrywa dla Ciebie wiele brudnych szczegółów i pozwala uzyskać dostęp do a wartości, na których zależy ci używanie notacji typu: a <- ma. Warto spojrzeć na State a monada, aby zobaczyć jak bind omija dla ciebie stan za kulisami. Podobnie tutaj, podczas łączenia parserów, najważniejsze są wartości, które parser powinien rozpoznać ... bind ukrywa całą brudną robotę, która wiąże się z łańcuchami pozostałymi po rozpoznaniu wartości typu a.