解析器组合器的类型 [英] Types for parser combinators

问题描述

如果我有一个解析器 a：Parser A 和一个解析器 b：Parser B ，那么我可以将它合并到解析器 a |中b：解析器（或者A B）。这可以起作用，但是当你开始添加更多的选择并获取类型如 A（B或C）时会有点棘手。我可以想象将以前的类型变成类似于 Alternative A B C 的东西。是否可以执行标准转换？或者我坚持为 Alternative ABC ... 类型生成一大堆样板。

<因此，关于或者的有趣之处在于，您可以将它用作类型级别的 cons 运算符。

  A'Either`（B`Either`（C`Either`） （D`Either`Void））） - > [A，B，C，D] 
  

所以我们所需要做的就是明确表示。您需要ghc-7.8才能支持封闭的数据族：

  { - ＃LANGUAGE TypeFamilies＃ - } 
 { - ＃LANGUAGE TypeOperators＃ - } 
 { - ＃LANGUAGE DataKinds＃ - } 
  -  ... 
 
类型系列OneOf（as :: [*]）:: *其中
 OneOf'[a] = a 
 OneOf（a'：as）=或者（OneOf as）
  

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

$ $ $ $ $ $ $ $ $ aorborc :: Parser（OneOf' [A，B，C]）
aorborc = a | （b | c）

仍然 所以你仍然可以轻松地与所有使用或者的代码进行互操作，这很好。

If I have a parser a : Parser A and a parser b : Parser B then I can combine it into a parser a | b : Parser (Either A B). This works but gets a little tricky when you start adding more alternatives and getting types like Either A (Either B C). I can imagine flattening the previous type into something like Alternative A B C. Is there a standard transformation I can perform or am I stuck with generating a whole bunch of boilerplate for types like Alternative A B C ....

解决方案

So the interesting thing about Either is that you can use it as a type-level cons operator.

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

So all we need do is make that explicit. You'll need ghc-7.8 to support closed data families:

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

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

Now you can write your types much more succinctly:

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

It's still Either under the hood, so you can still easily interoperate with all existing code that uses Either, which is nice.

这篇关于解析器组合器的类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！