Applicative解析器陷入无限循环：Alternative实例实现差异原因咨询

Let's break down what's happening here—this is a classic gotcha with Haskell's lazy evaluation, and while the two <|> implementations look logically identical, their behavior diverges dramatically because of when pattern matching triggers evaluation.

Your Problem Code #

First, here's the problematic Alternative instance that caused the infinite loop:

instance Alternative Parser where
  empty = Parser $ \_s -> []
  (Parser p1) <|> (Parser p2) = Parser $ \s -> case p1 s of [] -> p2 s ; xs -> xs

The Fixed Implementation #

And here's the version that works correctly:

instance Alternative Parser where
  empty = Parser $ \_s -> []
  p1 <|> p2 = Parser $ \s -> case runParser p1 s of [] -> runParser p2 s ; xs -> xs

The Root Cause: Lazy Evaluation & Pattern Matching Timing #

The key difference is when you unpack the Parser constructor:

1. In the broken version, you use pattern matching (Parser p1) <|> (Parser p2) immediately when defining the <|> operator. This forces Haskell to evaluate the input parsers right away to extract their internal p1 and p2 functions.
2. In the working version, you leave the parsers as opaque values (p1 and p2) and only unpack them when you call runParser later, during actual input parsing.

When you use some $ char 'A', remember that some is defined recursively:

some p = (:) <$> p <*> some p <|> empty

With the broken <|> implementation, when constructing the recursive some p branch, Haskell has to immediately unpack some p to get its internal function. But some p refers back to itself, so this triggers an infinite chain of unpacking/evaluation before you even get to run the parser—hence the infinite loop.

In the working implementation, the recursive some p branch stays unevaluated until it's actually needed. When parsing "AAA", the first branch (:) <$> char 'A' <*> some 'A' succeeds every time, so the <|> empty branch is never evaluated at all. Lazy evaluation keeps the recursion in check by only computing what's necessary.

Quick Takeaways #

• Avoid pattern-matching on your Parser constructor in combinator definitions unless you're sure it won't trigger recursive evaluation.
• Use your accessor function (runParser) to unpack parsers at the last possible moment—this preserves Haskell's lazy evaluation benefits and prevents unexpected infinite loops.

内容的提问来源于stack exchange，提问作者shouya