parsing - 解析器组合器的类型

Question

如果我有一个解析器 a : Parser A 和一个解析器 b : Parser B 那么我可以将它组合成一个解析器 a | b:解析器(A B 均可)。这可行，但当您开始添加更多替代方案并获取诸如 Either A (Either B C) 之类的类型时，会变得有点棘手。我可以想象将以前的类型扁平化为诸如Alternative A B C之类的东西。是否有我可以执行的标准转换，或者我是否坚持为 Alternative A B C ... 等类型生成一大堆样板。

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 的现有代码进行互操作，这很好。