我试图通过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是错的
如何修复此错误？
1条答案
按热度按时间67up9zun1#
我们假设
并考虑呼叫
(The字符串在这里实际上并不重要，
many singleSpaceParser调用将始终循环。）一个还原步骤产生
现在注意到，为了减少对
(<|>)的调用，我们必须将(<|>)的两个参数都计算为Parser ...的形式。让我们考虑一下
(:) <$> singleSpaceParser <*> many singleSpaceParser的情况，因为(<$>)和(<*>)都是infixl 4，所以这是<*>在最外层的应用。但是现在观察到，为了约简
(<*>)，我们必须再次计算(<*>)的两个参数，使其具有Parser ...的形状，因此特别是递归调用many singleSpaceParser。这就是我们得到无限循环的地方。
通过将
data切换到newtype（或者，至少避免在所有第二个参数中对Parser构造函数进行积极的模式匹配），可以避免这些问题。