应用解析器陷入无限循环

Question

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

{-# 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

事实“星”：在您执行中(<*>)：

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 []，但由于实际上是“管懒”，这是所有我们需要检查-我们可以相信，some_v <|> pure []是Parser _没有第一递归检查some_v和pure []。

（接下来，您将了解newtype-，从更改为时，又会感到困惑data，newtype使两种实现都起作用！）