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")]，但实际上它有一个无限循环

我用trace调试了一下，好像是many错误的

我该如何修复这个错误？

Answer 1

我们假设

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

并考虑通话

many singleSpaceParser "  123"

（这里的字符串实际上并不重要，many singleSpaceParser调用将始终循环。）

一步还原得到

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

现在观察到，为了减少对 的调用(<|>)，我们必须将 的两个参数评估(<|>)为形状Parser ...。

让我们考虑这样做(:) <$> singleSpaceParser <*> many singleSpaceParser。由于 和(<$>)都是(<*>)，因此这是最外层infixl 4的应用程序。<*>

但现在观察到，为了减少(<*>)，我们必须再次评估 的两个参数的(<*>)形状Parser ...，特别是递归调用many singleSpaceParser。

这就是我们得到无限循环的地方。

通过切换data到newtype（或者至少避免Parser在所有第二个参数中对构造函数进行积极的模式匹配），可以避免这些问题。