在 SML 中匹配两个自定义数据类型

Question

我有两个自定义数据类型，

datatype expression = Constant of int
                    | Variable of string
                    | Operator of string * expression
                    | Pair of expression list
                    | List of expression list

datatype pattern = ConstantP of int
                 | VariableP of string
                 | OperatorP of string * pattern
                 | PairP of pattern list
                 | ListP of pattern list
                 | UnorderedListP of pattern list
                 | Wildcard

我应该实现一个功能

match (fn : expression * pattern -> (string * expression) list option)

得到一个表达式和一个模式。如果可以匹配，则 returns SOME (list of bindings)，否则 returns NONE.

应该这样匹配：

匹配是在表达式和列表（表达式 * 模式）的元组上定义的。 Expression 和 Pattern 可以匹配也可以不匹配。如果是这样，则匹配会生成一个绑定列表 - 名称和值对（（字符串 * 表达式）列表），列表的顺序无关紧要。匹配使用以下规则：

通配符 匹配任何内容并生成一个空的绑定列表。
VariableP s 匹配任何值 v 和 returns 具有一个绑定 (s, v) 的列表。每个变量名 s 在每个模式中最多出现一次。
ConstantP 42 仅匹配 Constant 42 并生成一个空的绑定列表。对于其余的整数，它以相同的方式工作。
PairP [a1, a2] 匹配表达式 Pair [b1, b2] 如果 a1 匹配 b1 且 a2 匹配 b2。匹配会生成两个匹配项的串联列表。
ListP ps 匹配表达式列表 xs，如果 xs 中的每个值都匹配 ps 中的相应模式。该匹配项生成一个列表，我们通过连接所有匹配项接收到的绑定获得该列表。
OperatorP(a, x)匹配表达式Operator(b, y)，如果运算符a和b的名称相同且"x"匹配"y"。匹配产生了我们通过匹配 x 和 y 得到的绑定列表。

如果你能告诉我一些提示ps该往哪个方向走，我想我的函数应该是这样的，但我不确定递归地覆盖所有情况

fun match(e: expression, p: pattern) : (string * expression) list option =
    case p of 
         Wildcard => SOME []
       | VariableP s => ...

Answer 1

使用更多的模式匹配。
然后你一条一条地浏览规则列表并翻译它们，当规则依赖于子匹配时递归。
您只需要定义匹配构造函数的情况，将不匹配留给最后一个默认情况。

fun match (_, Wildcard) = SOME []
  | match (Constant x, ConstantP y) = if x = y then SOME [] else NONE
  | match (Pair [p1, p2], PairP [p1', p2']) = 
                                  let 
                                      val match1 = match (p1, p1')
                                  in case match1 of
                                         NONE => NONE
                                       | SOME ls => ...
                                  end
  | ...
  | match _ = NONE

但是您可以通过定义一些辅助函数来使事情变得更方便。
（上面的 Pair 子句在你全部输入后会变得笨拙。）

例如，仅当两个可选列表都不是时才连接两个可选列表 NONE 可以非常简洁地写成一个函数：

fun appendOptional (SOME xs, SOME ys) = SOME (xs @ ys)
  | appendOptional _ = NONE

并让你写一行

  | match (Pair[p1, p2], PairP[p1', p2']) = appendOptional(match(p1, p1'), match(p2, p2'))

并且该功能在其他情况下也可能派上用场。
（如果没有辅助函数，列表规则很痛苦，如果不是不可能的话。）

一个更详细的例子：

datatype expression =  Constant of int
                     | Variable of string
                     | Pair of expression list

datatype pattern = ConstantP of int
                 | VariableP of string
                 | PairP of pattern list
                 | Wildcard

fun appendOptional (SOME xs, SOME ys) = SOME (xs @ ys)
  | appendOptional _ = NONE

fun match (_, Wildcard) = SOME []
  | match (Constant x, ConstantP y) = if x = y then SOME [] else NONE
  | match (Pair [p1, p2], PairP [p1', p2']) = appendOptional (match (p1, p1'), match (p2, p2'))
  | match (e, VariableP v) = SOME [(v, e)] 
  | match _ = NONE

测试：

- match (Constant 32, ConstantP 1);
val it = NONE : (string * expression) list option

- match (Constant 32, ConstantP 32);
val it = SOME [] : (string * expression) list option

- match (Constant 32, VariableP "x");
val it = SOME [("x",Constant 32)] : (string * expression) list option

- match (Pair [Constant 32, Variable "y"], PairP [VariableP "a", VariableP "b"]);
val it = SOME [("a",Constant 32),("b",Variable "y")]
  : (string * expression) list option

在 SML 中匹配两个自定义数据类型

Match two custom datatypes in SML

pattern-matching

sml

ml