Haskell 中的递归解析器

Question

我正在 Haskell 中编写一个解析器，其中一个解析函数 (prefixParser) 应该 return 在每次调用时对其自身进行修改。这里的代码是简化的，但我希望包含所有必要的信息。

type MyParsec r = Parsec [Char] () Identity r

newtype SomeResult = String

newtype RecursiveParser = MyParsec (SomeResult, RecursiveParser)

items :: RecursiveParser -> MyParsec [SomeResult]
items prefixParser = do
  (someResult, newPrefixParser) <- prefixParser
  rst <- items newPrefixParser
  return (someResult : rst)

现在的问题是 prefixParser 的类型是 RecursiveParser 但我在需要 MyParsec 的 do 块中调用它。因此，我得到一个

Couldn't match expected type

错误。我什至可以做这样的事情还是我（像往常一样）不太了解 Haskell 的类型系统？

（prefixParser 用于解析递增数字 [1. 2. 3. ...]，目前尚未实现。）

Answer 1

这是错误的：

newtype RecursiveParser = MyParsec (SomeResult, RecursiveParser)

上面，MyParsec是一个新的数据构造函数的名称，与MyParser类型构造函数完全无关。本质上，上面的定义将 RecursiveParser 定义为一对 (SomeResult, RecursiveParser)，包裹在新构造函数 MyParsec.

下

回想一下 newtype 语法是

newtype NewtypeName = NewConstructorName SomeType

要实际使用MyParsec (...)类型，您需要指定构造函数的名称，如下所示。通常使用与 newtype 本身相同的名称来命名它。

newtype RecursiveParser = RecursiveParser (MyParsec (SomeResult, RecursiveParser))

然后，您可以调整代码以删除包装数据构造函数。

items :: RecursiveParser -> MyParsec [SomeResult]
items (RecursiveParser prefixParser) = do
  (someResult, newPrefixParser) <- prefixParser
  rst <- items newPrefixParser
  return (someResult : rst)

Haskell 中的递归解析器

Recursive Parser in Haskell

haskell

parsec