应用解析器陷入无限循环 [英] Applicative parser stuck in infinite loop
问题描述
我正在尝试实现自己的Applicative解析器,这是我使用的代码:
I'm trying to implement my own Applicative parser, here's the code I use:
{-# 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"
当我运行它时,它卡住了,再也不会返回.在深入研究问题之后,我指出了根本原因是我对<|>
方法的实现.如果我使用以下实现,那么一切都会按预期进行:
When I run it, it gets stuck and never returns. After digging into the problem I pinpointed the root cause to be my implementation of the <|>
method. If I use the following implementation then everything goes as expected:
instance Alternative Parser where
empty = Parser $ \_s -> []
p1 <|> p2 = Parser $ \s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs
在我的理解中,这两个实现是相当等效的.我猜想这可能与Haskell的惰性评估方案有关.有人可以解释发生了什么事吗?
These two implementations are, in my understanding, quite equivalent. What I guess is that this may have something to do with Haskell's lazy evaluation scheme. Can someone explain what's going on?
推荐答案
事实星":在您实现(<*>)
的过程中:
Fact "star": in your implementation of (<*>)
:
Parser p1 <*> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个参数实际上是Parser
构造函数对某些事物的应用,然后才可以进入等式的右侧.
...we must compute enough to know that both arguments are actually applications of the Parser
constructor to something before we may proceed to the right-hand side of the equation.
事实管道严格":在此实现中:
Fact "pipe strict": in this implementation:
Parser p1 <|> Parser p2 = ...
...我们必须进行足够的计算,才能知道两个解析器实际上都是Parser
构造函数的应用程序,然后才可以进入等号的右侧.
...we must compute enough to know that both parsers are actually applications of the Parser
constructor to something before we may proceed to the right-hand side of the equals sign.
事实懒惰":在此实现中:
Fact "pipe lazy": in this implementation:
p1 <|> p2 = Parser $ ...
...我们可以继续进行等号的右侧,而无需对p1
或p2
进行任何计算.
...we may proceed to the right-hand side of the equals sign without doing any computation on p1
or 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
在某物上的应用–无限循环!
Let's take your first implementation, the one about which we know the "pipe strict" fact. We want to know if some_v
is an application of Parser
to something. Thanks to fact "star", we must therefore know whether pure (:)
, v
, and some_v <|> pure []
are applications of Parser
to something. To know this last one, by fact "pipe strict", we must know whether some_v
and pure []
are applications of Parser
to something. Whoops! We just showed that to know whether some_v
is an application of Parser
to something, we need to know whether some_v
is an application of Parser
to something -- an infinite loop!
另一方面,在第二种实现中,要检查some_v
是否为Parser _
,我们仍然必须检查pure (:)
,v
和some_v <|> pure []
,但是由于管道懒惰"这一事实,这就是我们需要检查的所有 ,我们可以确信some_v <|> pure []
是Parser _
,而无需先递归检查some_v
和pure []
是.
On the other hand, with your second implementation, to check whether some_v
is a Parser _
, we still must check pure (:)
, v
, and some_v <|> pure []
, but thanks to fact "pipe lazy", that's all we need to check -- we can be confident that some_v <|> pure []
is a Parser _
without first checking recursively that some_v
and pure []
are.
(接下来,您将学习newtype
,并且从data
更改为newtype
会使两者的实现工作再次困惑!)
(And next, you will learn about newtype
-- and be confused yet again when changing from data
to newtype
makes both implementation work!)
这篇关于应用解析器陷入无限循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!