Idris 解析器组合器 GADT

Question

我目前正致力于在 Idris 中实现一个简单的解析器组合器库，以学习该语言并更好地理解一般类型系统，但我无法理解 GADT 的声明和使用方式。我试图制定的解析器数据类型看起来像（在 Haskell 中）：type Parser a = String -> [(a,String)]，来自 this 论文。基本上，该类型是一个接受字符串和 returns 列表的函数。

在伊德里斯我有：

data Parser : Type -> Type where
    fail : a -> (String -> [])
    pass : a -> (String -> [(a,String)])

其中 fail 实例是一个总是失败的解析器（即 - 将是一个总是 returns 空列表的函数）并且 pass 实例是一个解析器一些符号。将上面的内容加载到解释器中时，出现错误，指出 List elem 与预期类型 Type 之间存在类型不匹配。但是当我用 :t String -> List Type 检查 repl 中解析器的返回类型时，我得到 Type，看起来应该可以工作。

如果有人能很好地解释为什么此数据声明不起作用，或者提供表示解析器数据类型的更好替代方法，我将不胜感激。

Answer 1

在定义你的数据类型解析器时，第一行是说这个类型接受一个类型和 returns 一个类型，在这种情况下它接受一个 a 和 returns 一个 Parser a.

因此，您的构造函数应该 return Parser a.

类似于 List，它采用 a 和 return 一个 List a。

您当前 return 在您的构造函数中使用的不是 Parser 类型 - 很容易看出 Parser 这个词没有出现在右侧。

除此之外，我不确定您如何最好地表示这一点。但是，已经有一些用 Idris 编写的解析器库，看看这些可能会有帮助吗？例如，看看这个库列表，首先提到的是解析器：- Idris libraries

Answer 2

在Haskell、

type Parser a = String -> [(a,String)]

不会创建新类型，它只是一个类型同义词。您可以在 Idris 中做类似的事情

Parser : Type -> Type
Parser a = String -> List (a, String)

然后将您的助手定义定义为 return Parser as:

的简单函数

fail : Parser a
fail = const []

pass : a -> Parser a
pass x = \s => [(x, s)]

Idris 解析器组合器 GADT

Idris parser combinator GADT

parsing

types

gadt

idris