Haskell Parser Comminator Infinite循环

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

我使用了跟踪来调试，看来许多是错误的，

我该如何修复此错误？

Answer 1

让我们假设

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

并考虑呼叫

many singleSpaceParser "  123"

（在此处实际上并不重要，许多单身paceparser呼叫将始终循环。）

一个减少步骤的收益

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

现在观察到，为了将呼叫减少到（ ＆lt; |＆gt;），我们必须评估（＆lt; |＆gt;）的两个参数，属于Shape parser ...。

让我们考虑为（:)＆lt; $＆gt;这样做。 SinglespaceParser＆lt;*＆gt;许多SinglesPaceParser。因为两个（＆lt; $＆gt;）和（＆lt;*＆gt;）是infixl 4，这是的应用程序＆lt;*＆gt;在最外层级别。

但是现在观察到，为了减少（＆lt;*＆gt;），我们再次必须评估>（＆lt;*＆gt;）的两个参数以达到形状解析器...，尤其是递归调用许多SinglesPaceParser。

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

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