1

我松散地遵循斯蒂芬迪尔的写你一个 Haskell来实现我自己的解析器。但是，我被困在调用并将进入无限循环的many地步some。我已经使用 将循环精确到解析器的fmap函数trace，但我无法弄清楚为什么会发生循环。查看and的源代码somemany，似乎唯一被调用的其他函数是<*>(通过liftA2), pureand <|>; 我尝试trace对所有这些函数进行调用，但这些函数都没有出现在 stdout 上。

我的解析器的基本部分如下所示：

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

item :: Parser Char
item = trace "item" Parser $ \s ->
  case s of
    [] -> []
    (x:xs) -> pure (x, xs)

instance Functor Parser where
  fmap f (Parser p) = trace "fmap" Parser $ fmap (first f) . p

instance Applicative Parser where
  (Parser p1) <*> (Parser p2) = trace "<*>" Parser $ 
    \s1 -> [(f x, s3) | (f, s2) <- p1 s1, (x, s3) <- p2 s2]
  pure x = trace "pure" Parser $ \s -> pure (x, s)


instance Alternative Parser where
  empty = trace "empty" Parser $ const mempty
  (Parser p1) <|> (Parser p2) = trace "<*>" Parser $ \s -> case p1 s of
    [] -> p2 s
    x  -> x

调用many或some显示以下输出：

> runParser (many item) "abcd"
item
fmap
fmap
fmap
(and so forth)

据我所知，我的功能已正确实现。为什么会fmap发生这种无限循环？

4

0 回答 0