I am trying to understand the behavior of many in the Megaparsec library for Haskell. I would have thought that many returns an empty list when its input parser fails, but this does not seem to be the case.
In particular, I am puzzled by the following, minimal code:
import Text.Megaparsec (Parsec, many, parseTest)
import Text.Megaparsec.Char (string)
import Data.Void
test :: Parsec Void String [String] -> String -> IO ()
test = parseTest
main = do
test (many (string "a" >> string "b")) "ac" -- error
test (many (string "a" <> string "b")) "ac" -- error
test (many (string "ab")) "ac" -- []
Its output is the following:
1:2:
|
1 | ac
| ^
unexpected 'c'
expecting 'b'
1:2:
|
1 | ac
| ^
unexpected 'c'
expecting 'b'
[]
I don't understand why the first two tests fail and the third one does not.
There's no difference in what the parsers string "a" >> string "b" and string "a" <> string "b" will parse, only in what they return when the parse is successful (which is "b" for the first versus "ab" for the second), so it's no surprise that the first two cases behave the same (i.e., both fail).
The reason they fail is that the parser many p runs the parser p until it fails. If the failure of p does not consume input, then many p succeeds and returns the list of results from the successful runs of parser p prior to its failure. If the failure of p consumes input, then many p fails with the same "reason" as the final failure of parser p.
When the parser string "a" >> string "b" runs on the input "ac", the string "a" parser successfully parses the "a", and then the string "b" parser fails to parse the "c", without consuming input. This causes the overall parser string "a" >> string "b" to fail, having consumed input (the input consumed by string "a", even though the parse causing the failure string "b" didn't itself consume any input).
Put this together, and many (string "a" >> string "b") runs the parser string "a" >> string "b" until it fails, which happens on the very first application with the reason that the parser string "b" expected a "b" but got a "c". Because this failure consumed input (the "a" consumed by string "a"), the whole parser many (string "a" >> string "b") fails with the same "reason".
The parser string "ab" is a little different, and its behavior differs between Parsec and versions of Megaparsec since 4.4.0 (see the documentation for tokens).
In Parsec, the parser string "ab" applied to the input "ac" consumes the "a" and then fails on the "c", so it fails after consuming input. This is probably a bad idea, which is why Parsec introduced string' in version 3.1.16.0. The parser string' "ab" does the more sensible thing: it either consumes all of "ab" or it fails without consuming anything. In particular, when it's applied to the input "ac" and can't consume "ab", it fails without consuming input.
In Megaparsec, string initially behaved like Parsec's string, but when they fixed this design flaw, instead of introducing a new string' combinator, they just made an incompatible change to string, so string "ab" in Megaparsec like string' "ab" in Parsec, either consumes all of "ab" or fails without consuming anything.
(To add to the confusion, Megaparsec also has a string' combinator, but it's a case insensitivie version of string and so has nothing to do with Parsec's version of string'.)