我正在尝试实现自己的应用解析器,这是我使用的代码:
{-# 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的惰性评估方案有关。有人可以解释发生了什么吗?
事实“星号:在您执行(<*>)
时:
Parser p1 <*> Parser p2 = ...
...我们必须进行足够的计算,才能知道两个参数实际上都是Parser
构造函数对某些事物的应用,然后才可以进入等式的右侧。
事实“管道严格”:在此实现中:
Parser p1 <|> Parser p2 = ...
...我们必须进行足够的计算,才能知道两个解析器实际上都是Parser
构造函数对某些事物的应用,然后才可以进入等号的右侧。
事实“懒惰”:在此实现中:
p1 <|> p2 = Parser $ ...
...我们可以继续进行等号的右侧,而无需对p1
或p2
进行任何计算。
这很重要,因为:
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 []
,但由于事实是“懒惰”,这是我们需要检查的[[all-我们可以确信some_v <|> pure []
是Parser _
,而无需先递归检查some_v
和pure []
是。
newtype
,当从data
更改为newtype
会使both]执行工作时再次感到困惑!]