It seems like endBy and endBy1 also need attention. This first test passes, but the next 2 fail:

  parseTest "a,a,a," (cons "a" (cons "a" (cons' "a" Nil))) $ do -- existing
    as <- string "a" `endBy1` string ","
    eof
    pure as
  parseTest "a,a,a" (cons "a" (cons' "a" Nil)) $ do -- new
    as <- string "a" `endBy1` string ","
    _ <- string "a"
    pure as
  parseTest "a,a,a" (Cons "a" (Cons "a" Nil)) $ do -- new
    as <- string "a" `endBy` string ","
    _ <- string "a"
    pure as

Or this is the intended behaviour of the combinators?

And I could be wrong, but do optional and option also need this? For both of these, if the supplied parser consumes input and fails then the alt behaviour will be skipped. I would be great to hear from someone with more experience. @garyb ?

  parseTest "ab" "ab" do
    optional (string "a" *> string "x")
    string "ab"

fails with Expected "x"

@robertdp Thank you for pointing these issues out. I have just checked the implementation of Haskell's Parsec library and found they cannot parse your new test cases either. Maybe my latest commit on endBy is not expected? I'd like to hear from @garyb too.

Btw, although adding try is the simplest way to fix sepBy and sepEndBy, I now realize this could lead to uninformative error messages. Is it better to rewrite them using the original mutual recursive style?

@yzyzsun Sorry for thinking aloud in your PR. I only just discovered this problem caused by my PR, so I've been digging into this lib and comparing it with Parsec to try and understand what I was missing.

This definitely needs input from the maintainers (and people who understand and use the lib) but I would suggest undoing all the changes from my PR, including removing the use of NonEmptyList. This puts it back to the Parsec-style mutually recursive implementation. If we want to have combinators that return NonEmptyList, they could be identically-named but in a new module called Text.Parsing.Parser.Combinators.NonEmpty.

-- Original combinator
sepEndBy1 :: forall m s a sep. Monad m => ParserT s m a -> ParserT s m sep -> ParserT s m (List a)
sepEndBy1 p sep = do
  a <- p
  (do _ <- sep
      as <- sepEndBy p sep
      pure (a : as)) <|> pure (singleton a)

-- NonEmpty wrapper
sepEndBy1 :: forall m s a sep. Monad m => ParserT s m a -> ParserT s m sep -> ParserT s m (NonEmptyList a)
sepEndBy1 p sep =
  C.sepEndBy1 p sep >>=
    case _ of
      Cons x xs -> pure (NEL.cons' x xs)
      _ -> unsafeCrashWith "expected non-empty list"
    

@robertdp Never mind about that! Actually I agree with your suggestion since it can easily bring everything back to order.

Thanks for kicking this off @yzyzsun!