应用程序解析器陷入无限循环
Applicative parser stuck in infinite loop
我正在尝试实现我自己的应用程序解析器,这是我使用的代码:
{-# 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"
当我 运行 它时,它会卡住并且永远不会 returns。在深入研究问题后,我确定根本原因是我对 <|>
方法的实现。如果我使用以下实现,那么一切都会按预期进行:
instance Alternative Parser where
empty = Parser $ \_s -> []
p1 <|> p2 = Parser $ \s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs
在我的理解中,这两个实现是相当等价的。我猜测这可能与 Haskell 的惰性评估方案有关。谁能解释一下这是怎么回事?
事实"star":在您的实施中(<*>)
:
Parser p1 <*> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个参数实际上是 Parser
构造函数对某些事物的应用,然后我们才能继续等式的右侧。
事实"pipe strict":在这个实现中:
Parser p1 <|> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个解析器实际上是 Parser
构造函数的应用程序,然后我们才能继续等号的右侧。
事实"pipe lazy":在此实施中:
p1 <|> p2 = Parser $ ...
...我们可以在不对 p1
或 p2
.
进行任何计算的情况下继续等号的右侧
这很重要,因为:
some v = some_v where
some_v = pure (:) <*> v <*> (some_v <|> pure [])
让我们以您的第一个实现为例,我们知道 "pipe strict" 事实。我们想知道 some_v
是否是 Parser
对某物的应用。由于事实 "star",我们因此必须知道 pure (:)
、v
和 some_v <|> pure []
是否是 Parser
对某物的应用。要知道最后一个,事实上 "pipe strict",我们必须知道 some_v
和 pure []
是否是 Parser
对某物的应用。哎呀!我们刚刚展示了要知道 some_v
是否是 Parser
对某物的应用,我们需要知道 some_v
是否是 Parser
对某物的应用——无限循环!
另一方面,对于您的第二个实现,要检查 some_v
是否是 Parser _
,我们仍然必须检查 pure (:)
、v
和 some_v <|> pure []
,但由于事实 "pipe lazy",我们需要检查 all——我们可以确信 some_v <|> pure []
是 Parser _
而没有首先递归检查 some_v
和 pure []
是。
(接下来,您将了解 newtype
—— 当从 data
更改为 newtype
时,您会再次感到困惑,这使得 both 实施工作!)
我正在尝试实现我自己的应用程序解析器,这是我使用的代码:
{-# 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"
当我 运行 它时,它会卡住并且永远不会 returns。在深入研究问题后,我确定根本原因是我对 <|>
方法的实现。如果我使用以下实现,那么一切都会按预期进行:
instance Alternative Parser where
empty = Parser $ \_s -> []
p1 <|> p2 = Parser $ \s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs
在我的理解中,这两个实现是相当等价的。我猜测这可能与 Haskell 的惰性评估方案有关。谁能解释一下这是怎么回事?
事实"star":在您的实施中(<*>)
:
Parser p1 <*> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个参数实际上是 Parser
构造函数对某些事物的应用,然后我们才能继续等式的右侧。
事实"pipe strict":在这个实现中:
Parser p1 <|> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个解析器实际上是 Parser
构造函数的应用程序,然后我们才能继续等号的右侧。
事实"pipe lazy":在此实施中:
p1 <|> p2 = Parser $ ...
...我们可以在不对 p1
或 p2
.
这很重要,因为:
some v = some_v where
some_v = pure (:) <*> v <*> (some_v <|> pure [])
让我们以您的第一个实现为例,我们知道 "pipe strict" 事实。我们想知道 some_v
是否是 Parser
对某物的应用。由于事实 "star",我们因此必须知道 pure (:)
、v
和 some_v <|> pure []
是否是 Parser
对某物的应用。要知道最后一个,事实上 "pipe strict",我们必须知道 some_v
和 pure []
是否是 Parser
对某物的应用。哎呀!我们刚刚展示了要知道 some_v
是否是 Parser
对某物的应用,我们需要知道 some_v
是否是 Parser
对某物的应用——无限循环!
另一方面,对于您的第二个实现,要检查 some_v
是否是 Parser _
,我们仍然必须检查 pure (:)
、v
和 some_v <|> pure []
,但由于事实 "pipe lazy",我们需要检查 all——我们可以确信 some_v <|> pure []
是 Parser _
而没有首先递归检查 some_v
和 pure []
是。
(接下来,您将了解 newtype
—— 当从 data
更改为 newtype
时,您会再次感到困惑,这使得 both 实施工作!)