differenza tra munch e molti (soddisfare p)?

Question

Nel modulo Text.ParserCombinators.ReadP, munch (e munch1) documentazione dice:

analizza i primi zero o più caratteri che soddisfano il predicato. Succede sempre, esattamente dopo aver consumato tutti i caratteri Quindi NON è lo stesso di (many (satisfy p)).

In che modo sono diversi?

Answer 1

Per prima cosa, troviamo un contro-esempio e usiamo gli strumenti Haskell per farlo automaticamente. La biblioteca QuickCheck ci può dare ad un contro-esempio molto rapidamente:

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 

Lo chiediamo di verificare, se i due parser much pred e many (satisfy pred) sono gli stessi. QuickCheck trova subito che sono diversi e cerca di produrre il più breve contro-esempio possibile:

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

Così munch pred consuma sempre 'a' incondizionatamente, mentre many (satisfy pred) dà una risposta non deterministica - si potrebbe o non potrebbe non consumano 'a'.

Si consideri ad esempio eseguendo i seguenti due parser su stringa "abcd":

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

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

Il primo non riesce, perché munch consuma l'intera stringa e quindi non è possibile abbinare "cd". Il secondo ha successo, perché many (satisfy ...) creare tutte le possibili rami

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

e string "cd" riesce sul ramo che consumava "ab".