解析器组合器的类型

Question

如果我有一个解析器 a : Parser A 和一个解析器 b : Parser B，那么我可以将它们组合成一个解析器 a | b : Parser (Either A B)。这个方法可行，但是当我开始添加更多的选择并得到像 Either A (Either B C) 这样的类型时，就会变得有点棘手。我可以想象将前一个类型平铺成类似于Alternative A B C 的形式。我能否执行标准转换或者我必须为像Alternative A B C ...这样的类型生成大量样板代码呢？

- David K.

---

你可以在这里使用“Data Types a la carte”方法，但我发现编写一个ADT来处理它会更容易且使用的样板代码更少。 - bheklilr

我突然想知道将来是否可以扩展GHC，使[]具有多元性，以便您可以将类型写为Alternative [A,B,C]。 - Ørjan Johansen

在这里，直接使用自定义数据类型来表示您想要的实际求和类型是最好的方法。 - AndrewC

Ørjan Johansen：未来已来 - rampion

@rampion 哦，你是对的！我最初只测试了:k []，似乎只允许*内容，但经过进一步测试，:k [Either Int, Maybe]等已经可以正常工作。 - Ørjan Johansen

Answer 1

关于 Either 的有趣之处在于，你可以将其作为类型级别的 cons 运算符使用。

A `Either` (B `Either` (C `Either` (D `Either` Void))) --> [A,B,C,D]

所以我们需要做的就是明确这一点。你需要ghc-7.8来支持封闭数据族：

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE DataKinds #-}
-- ...

type family OneOf (as :: [*]) :: * where
  OneOf '[a] = a
  OneOf (a ': as) = Either a (OneOf as)

现在您可以更简洁地编写类型：

aorborc :: Parser (OneOf '[A, B, C])
aorborc = a | (b | c)

它在内部仍然是Either，因此您仍然可以轻松地与使用Either的所有现有代码进行互操作，这很好。

- rampion

---

为避免（可能是不必要的）导入，省略了 OneOf '[] = Void。 - rampion

如果您按照我在这个答案中定义U的方式定义OneOf，则不需要使用Void。只需避免编写'[a]情况，并从'[a, b]开始即可。 - Christian Conkle

Christian Conkle：我是说我们需要像Data.Void这样的东西来定义OneOf '[]并使OneOf成为总体。跟随U的例子只会使它不那么完整，因为OneOf '[a]将不再被定义。 - rampion

Answer 2

Either只是Haskell中一种可能的总和类型，由于准备好的类实例和辅助函数在许多情况下都很有用，但是当您嵌套它时会变得相当笨重。

对于解析器最好的方法是创建自己的数据类型来镜像您正在解析的结构并直接解析进去。让我们举个玩具语言的部分例子。

data Statement = TypeDec String Type
                 DataDec String [Constructor]
                 FunctionDec String LambdaExpression

statement :: Parser Statement
statement = TypeDec <$> string "type " *> identifier <*> string " = " *> type
            <|> DataDec <$> string "data " *> identifier <*> string " = " *> many constructor
            <|> FunctionDec <$> identifier <*> string " = " *> lambdaExpression

以这种方式，您的数据结构和代码都反映了您正在解析的语法中的产生物。这样做的巨大好处是您的数据类型安全、清晰并且一旦解析就可以立即使用。 _{（我总是无法记住*>和<*的优先级，所以我可能已经用需要括号或其他东西的方式来完成它，但希望您能理解我的意思。）}

- AndrewC