ocaml - Flow Parser AST 上模式匹配的一般策略

问题描述

我正在开发一个使用流解析器的项目。我对 OCaml 有点陌生，所以所有参数化类型都让我头晕目眩。鉴于这个简单的例子：

utop # Parser_flow.program "let x;";;
- : Loc.t Ast.program * (Loc.t * Parse_error.t) list =
(({Loc.source = None; start = {Loc.line = 1; column = 0; offset = 0};
   _end = {Loc.line = 1; column = 6; offset = 6}},
  [({Loc.source = None; start = {Loc.line = 1; column = 0; offset = 0};
     _end = {Loc.line = 1; column = 6; offset = 6}},
    Ast.Statement.VariableDeclaration
     {Ast.Statement.VariableDeclaration.declarations =
       [({Loc.source = None; start = {Loc.line = 1; column = 4; offset = 4};
          _end = {Loc.line = 1; column = 5; offset = 5}},
         {Ast.Statement.VariableDeclaration.Declarator.id =
           ({Loc.source = None; start = {Loc.line = 1; column = 4; offset = 4};
             _end = {Loc.line = 1; column = 5; offset = 5}},
            Ast.Pattern.Identifier
             {Ast.Pattern.Identifier.name =
               ({Loc.source = None;
                 start = {Loc.line = 1; column = 4; offset = 4};
                 _end = {Loc.line = 1; column = 5; offset = 5}},
                "x");
              typeAnnotation = None; optional = false});
          init = None})];
      kind = Ast.Statement.VariableDeclaration.Let})],
  []),
 [])

仅考虑Loc.t Ast.program部分：soAst.program是由参数化的Loc.t，我想我遵循了这么多：

type nonrec 'M program = 'M * 'M Ast.Statement.t list * 'M Ast.Comment.t list

现在只考虑语句列表，假设我想单步执行并为每个打印一些东西VariableDeclaration，例如。我将如何匹配该构造？我可以做类似的事情：

(** x is an element of Loc.t Ast.Statement.t list *)
let match_test x =
  match x with
    | (Loc.t l, Ast.Statement.VariableDeclaration b) -> print_string "declaration!"
    | _ -> print_string "no declaration!"

感谢您的任何指示/帮助！

标签： ocamlflowtype

解决方案

OCaml 模式匹配与代数数据类型一起构成了一种强大的数据语言，可以轻松编码和处理复杂的数据结构。这使得 OCaml 成为分析结构数据的好工具。令人惊讶的是，模式匹配在主流语言中并不是很常见，所以这个概念有时会让人感到困惑。让我试着用简单的例子来解释它，然后我们可以转向更复杂的东西。

要构造数据，我们需要定义数据构造函数。数据构造函数表示创建给定类型的值的不同可能方式。这就是为什么它们通常也被称为变体。例如，

type image = 
 | Circle of int
 | Rectangle of int * int
 | Row of image * image
 | Column of image * image
 | Layer of image * image

半径为 10 的圆表示为Circle 10，我们可以使用将一个圆放在另一个圆的顶部Layer (Circle 10, Circle 5)，例如，

# let eye = Layer (Circle 10, Circle 5);;
val eye : image = Layer (Circle 10, Circle 5)

我们现在有一个image名为的类型的对象eye。OCaml 顶层很适合为我们打印它，作为人类，我们可以很容易地看到它的布局。但作为程序员，我们需要对其进行分析。我们需要解构图像以查看它是从哪些部分构建的。为了解构一个对象，我们使用与构造它相同的语法，除了我们将结构写在等号的左侧，将我们解构的对象写在右侧，例如，

let Layer (Circle 10, Circle 5) = eye

如果我们在 OCaml 顶层输入它，它会同意我们，但会发出警告，比如，如果eye对象不是两个圆圈的层怎么办？或者什么圆有不同的半径？在这种情况下，我们无法解构眼睛对象，我们的程序将失败。所以我们需要以某种方式能够考虑所有的可能性，首先，让我们学习如何匹配任何大小的眼睛，例如，

let Layer (Circle _, Circle _) = eye

这种模式将与任何大小的眼睛相匹配。我们使用了通配符模式_，表示“与我不关心的任何内容匹配”。但是如果我们关心，如果我们想匹配任何尺寸，但仍然能够知道它们怎么办？这就是绑定匹配发挥作用的地方，我们可以在模式中使用变量而不是数据构造函数，当匹配发生时，变量将引用相应位置的对象，例如，

 # let Layer (Circle outer, Circle inner) = eye
 val outer : int = 10
 val inner : int = 5

现在我们可以使用outer和inner变量，例如，

 assert (outer > inner)

现在，不是只匹配给定配置的一只眼睛，我们可以匹配无数不同的眼睛，但仍然只有眼睛（即两层圆圈）。

终于到了介绍匹配表达式的时候了，

# let what_is_that = 
    match eye with
    | Layer (Circle _, Circle _) -> "an eye"
    | _ -> "I don't know
val what_is_that : string = "an eye"

现在 OCaml 终于高兴了，因为我们分析了所有可能的图像，所以没有发出警告。通常，匹配表达式具有以下形式

 match <exp> with
 | <pat1> -> <e1>
 | <pat2> -> <e2>
 ...
 | <patN> -> <eN>

当它被评估时，表达式所<exp>表示的对象被分析并且所有的模式都被应用在一个序列中，直到找到一个匹配的模式，然后匹配模式右边的表达式被评估并且它可以使用任何绑定在这个模式中的变量。这个表达式的结果然后成为整个match表达式的结果。为了巩固这些知识，让我们写一些有意义的东西，比如计算图像边界框的函数，例如，

let rec bounding_box image = match image with
  | Circle r -> 2*r,2*r
  | Rectangle (h,w) -> h,w
  | Row (left,right) ->
    let hl,wl = bounding_box left
    and hr,wr = bounding_box right in
    max hl hr, wl + wr
  | Column (top,bot) ->
    let ht,wt = bounding_box top
    and hb,wb = bounding_box bot in
    ht + hb, max wt wb
  | Layer (x,y) ->
    let hx,wx = bounding_box x
    and hy,wy = bounding_box y in
    max hx hy, max wx wy

这是它的工作原理，

# bounding_box eye;;
- : int * int = (20, 20)

# bounding_box (Row (eye,eye));;
- : int * int = (20, 40)

此外，什么是(20,20)？它被称为元组，是构造对、三元组等的内置方式。我们当然可以定义我们自己的配对，比如

type pair = Pair of int * int

甚至使它成为多态数据结构，例如，

type ('a,'b) = Pair of 'a * 'b

然后对三重、四重等重复相同的操作。但是语言的设计者认为它太麻烦了，因为元组的数量很容易用逗号的数量来描述，所以我们可以在没有任何特定命名构造函数的情况下构造元组。否则，元组按照相同的规则运行，并使用相同的语法构造和解构，例如，

let 4, 3 = 2*2, 4-1

括号是可选的，但经常使用，因为逗号运算符的优先级很低。因此，人们总是倾向于使用括号，例如，

let (4, 3) = (2*2, 4-1)

虽然元组非常方便，但缺少名称很容易忘记哪个元素意味着什么。就像我什至不确定bounding_box上面的函数是否正确，我也没有在某处将宽度与高度混淆。此外，这个函数返回什么甚至都不明显。所以这里来记录。记录是具有命名字段的元组。例如，

type box = {height : int; width : int}

现在我们可以使用新box类型来重写bounding_box函数了。用它来构造我们的矩形也是一个不错的选择，例如，我们可以将Rectangle构造函数重新定义为| Rectangle of box. 但我会把它作为一个练习给读者。

我希望，这些信息应该足以开始使用模式匹配而不必担心。您还可以考虑查看此示例以获得一些灵感。

ocaml - Flow Parser AST 上模式匹配的一般策略

问题描述

解决方案

推荐阅读