разница между munch и многими (удовлетворить p)?

Question

В модуле Text.ParserCombinators.ReadP, munch (и munch1) документация говорит:

Анализирует первые ноль или более символов, удовлетворяющих предикату. Всегда успешно, ровно один раз, потребляя все символы. Следовательно, НЕ то же самое, что и (many (satisfy p)).

Как они отличаются?

Answer 1

Прежде всего, давайте найдем встречный пример и давайте использовать инструменты Haskell для этого автоматически. QuickCheck библиотека может дать нам такую ​​контрпример очень быстро:

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 

Мы просим его, чтобы проверить, являются ли два парсеры much pred и many (satisfy pred) одинаковы. QuickCheck сразу обнаруживает, что они разные, и пытается произвести короткий контрпример как можно:

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

Так munch pred всегда потребляет 'a' безоговорочно, в то время как many (satisfy pred) дает недетерминированную ответ - это может или не может не потреблять 'a'.

Для примера рассмотрим, выполнив следующие два парсера на строку "abcd":

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

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

Первый терпит неудачу, потому что munch потребляет всю строку, а затем это не представляется возможным, чтобы соответствовать "cd". Второй один преуспевает, потому что many (satisfy ...) создает все возможные ветви

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

и string "cd" преуспевает на ветке, которая поглотила "ab".