应用程序解析器陷入无限循环

Question

我正在尝试实现我自己的Applicative解析器，下面是我使用的代码：

{-# LANGUAGE ApplicativeDo, LambdaCase #-}
module Parser where
-- Implementation of an Applicative Parser
import Data.Char
import Control.Applicative (some, many, empty, (<*>), (<$>), (<|>), Alternative)
data Parser a = Parser { runParser :: String -> [(a, String)] }
instance Functor Parser where
-- fmap :: (a -> b) -> (Parser a -> Parser b)
fmap f (Parser p) = Parser (s -> [(f a, s') | (a,s') <- p s])
instance Applicative Parser where
-- pure :: a -> Parser a
-- <*> :: Parser (a -> b) -> Parser a -> Parser b
pure x = Parser $ s -> [(x, s)]
(Parser pf) <*> (Parser p) = Parser $ s -> 
[(f a, s'') | (f, s') <- pf s, (a, s'') <- p s']
instance Alternative Parser where
-- empty :: Parser a
-- <|> :: Parser a -> Parser a -> Parser a
empty = Parser $ _s -> []
(Parser p1) <|> (Parser p2) = Parser $ s ->
case p1 s of [] -> p2 s
xs -> xs
char :: Char -> Parser Char
char c = Parser $ case (c':cs) | c == c' -> [(c,cs)] ; _ -> []
main = print $ runParser (some $ char 'A') "AAA"

当我运行它时，它会卡住，再也回不来了。在深入研究了这个问题之后，我确定了根本原因是我实现了<|>方法。如果我使用以下实现，那么一切都如预期：

instance Alternative Parser where
empty = Parser $ _s -> []
p1 <|> p2 = Parser $ s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs

在我看来，这两种实现是相当等价的。我想这可能与Haskell的懒惰评估方案有关。有人能解释一下发生了什么吗？

Answer 1

Fact"star"：在(<*>):的实现中

Parser p1 <*> Parser p2 = ...

我们必须进行足够的计算，以知道这两个参数实际上都是CCD_。

事实"管道严格"：在此实现中：

Parser p1 <|> Parser p2 = ...

我们必须进行足够的计算，以知道两个解析器实际上都是Parser构造函数对某个事物的应用，然后才能继续进行等号的右侧。

事实"管道懒惰"：在此实现中：

p1 <|> p2 = Parser $ ...

我们可以在不对CCD_ 5或CCD_。

这很重要，因为：

some v = some_v where
some_v = pure (:) <*> v <*> (some_v <|> pure [])

让我们来看看您的第一个实现，即我们所知道的"管道严格"事实。我们想知道some_v是否是Parser在某些方面的应用。由于"星"这个事实，我们必须知道pure (:)、v和some_v <|> pure []是否是Parser对某些事物的应用。要知道最后一个，实际上是"管道严格"的，我们必须知道some_v和pure []是否是Parser对某些事物的应用。哇！我们刚刚证明，要知道some_v是否是Parser对某个事物的应用，我们需要知道some_v是否是Parser对某个东西的应用——一个无限循环！

另一方面，对于您的第二个实现，要检查some_v是否是Parser _，我们仍然必须检查pure (:)、v和some_v <|> pure []，但由于事实上"管道懒惰"，这就是我们需要检查的全部——我们可以确信some_v <|> pure []是Parser _，而无需首先递归检查some_v和pure []是。

(接下来，您将了解newtype——当从Parser0更改为newtype使两个实现工作时，您将再次感到困惑！(