różnica między munch i wiele (spełniają p)?

Question

W module Text.ParserCombinators.ReadP, munch (i munch1) dokumentację mówi:

analizuje pierwsze zero lub więcej znaków spełniających predykat. Zawsze udaje się, dokładnie raz pochłonął wszystkie znaki, dlatego NIE jest taki sam jak (many (satisfy p)).

Czym się różnią?

Answer 1

Najpierw znajdźmy kontrprzykład i użyjmy narzędzi Haskella, aby zrobić to automatycznie. Biblioteka QuickCheck może dać nam taki kontrprzykład bardzo szybko:

import Data.Function (on) 
import Text.ParserCombinators.ReadP 
import Test.QuickCheck 

prop_ParseTest :: String -> Property 
prop_ParseTest input = on (===) runParser (munch pred) (many (satisfy pred)) 
    where 
    runParser :: ReadP a -> [(a, String)] 
    runParser = flip readP_to_S input -- run a given parser on a given input 
    pred :: Char -> Bool 
    pred = (> 'A') 

main :: IO() 
main = quickCheck prop_ParseTest 

Pytamy go przetestować, czy oba Parsery much pred i many (satisfy pred) są takie same. QuickCheck natychmiast stwierdza, że ​​są one różne i stara się produkować jak krótkie kontrprzykład jak to możliwe:

*** Failed! Falsifiable (after 5 tests and 2 shrinks):  
[("a","")] /= [("","a"),("a","")] 

Więc munch pred zawsze zużywa 'a' bezwarunkowo, natomiast many (satisfy pred) daje niedeterministycznych odpowiedź - to może lub nie może nie zużywają 'a'.

Rozważmy na przykład uruchamiając następujące dwa parser na ciąg "abcd":

test1 = munch (> 'A') >> string "cd" 

test2 = many (satisfy (> 'A')) >> string "cd" 

Pierwszy zawiedzie, ponieważ munch zużywa cały ciąg i to nie jest możliwe, aby dopasować "cd". Drugi powiedzie, ponieważ many (satisfy ...) tworzy wszystkie możliwe branże

[("","abcd"),("a","bcd"),("ab","cd"),("abc","d"),("abcd","")] 

i string "cd" powiedzie na gałęzi, które spożywane "ab".