Haskell解析器组合器无限循环。

Question

我正在尝试通过Haskell编写一个简单的解析器，但卡在了一个无限循环中。 代码如下：

import Control.Applicative (Alternative, empty, many, (<|>))

data Parser a = Parser {runParser :: String -> [(a, String)]}

instance Functor Parser where
  fmap f (Parser p) = Parser $ \s -> [(f x', s') | (x', s') <- p s]

instance Applicative Parser where
  pure x = Parser $ \s -> [(x, s)]
  (Parser pf) <*> (Parser p) = Parser $ \s -> [(f' x, ss') | (f', ss) <- pf s, (x, ss') <- p ss]

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

singleSpaceParser :: Parser Char
singleSpaceParser = Parser $ \s ->
  ( case s of
      x : xs -> if x == ' ' then [(' ', xs)] else []
      [] -> []
  )

multiSpaceParser :: Parser [Char]
multiSpaceParser = many singleSpaceParser

我只需在ghci中加载此文件并运行：

runParser multiSpaceParser "  123"

我期望它会得到 [(" ", "123")]，但实际上它陷入了一个无限循环。

我使用跟踪来调试，似乎 many 的值不正确。

我该如何修复这个 bug？

- yixing

---

many 处理 Alternative，这意味着它将首先尝试 singleSpaceParser，如果失败了，它会尝试另一个 singleSpaceParser 等。 - Willem Van Onsem

所以问题是multiSpaceParser会调用无限的'singleSpaceParser'吗？如果第一个'singleSpaceParser'失败了，为什么它还要尝试另一个'singleSpaceParser'呢？ - yixing

这是一个相当微妙的由于懒惰引起的问题。如果你将 data 替换为 newtype，它应该可以工作。 - kosmikus

Answer 1

假设

many p = (:) <$> p <*> many p <|> pure []

考虑该调用

many singleSpaceParser "  123"

（该字符串实际上并不重要，许多singleSpaceParser调用总是循环执行。）

一个化简步骤产生

   ((:) <$> singleSpaceParser <*> many singleSpaceParser <|> pure []) "  123"

现在注意到，为了减少调用(<|>)，我们必须评估(<|>)的两个参数都是Parser ...的形状。

让我们考虑对(:) <$> singleSpaceParser <*> many singleSpaceParser进行这样的操作。由于(<$>)和(<*>)都是infixl 4，因此这是在最外层应用<*>。

但现在请注意，为了减少(<*>)，我们再次必须评估(<*>)的两个参数都是Parser ...的形状，因此尤其包括递归调用many singleSpaceParser。

这就是我们产生无限循环的地方。

通过将data切换为newtype（或者至少不要过于依赖第二个参数中的Parser构造函数的模式匹配），可以避免这些问题。

- kosmikus

---

将“data”更改为“newtype”后，我解决了这个问题，非常感谢 :) - yixing

然后通过 StateT String [] 进行 deriving (Functor, Applicative, Alternative, Monad)。 - Iceland_jack

你也可以使用 - 使 <*> 更加懒惰 - pf <*> p = Parser $ \s -> [(f' x, ss') | (f', ss) <- runParser pf s, (x, ss') <- runParser p ss] - Anupam Jain

或者，使用~使<*>更懒惰：~(Parser pf) <*> ~(Parser p) = ... - Franky