Match two custom datatypes in SML

Question

I have two custom datatypes,

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

I should implement a function

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

that gets an expression and a pattern. If match is possible, it returns SOME (list of bindings), otherwise it returns NONE.

Matching should be done in this way:

A match is defined on a tuple of an expression and a list (expression * pattern). Expression and Pattern can either match or not. If they do, the match produces a list of bindings - pairs of names and values ((string * expression) list), the ordering of the list does not matter. Matching uses the following rules:

• Wildcard matches anything and produces an empty list of bindings.
• VariableP s matches any values v and returns a list with one binding (s, v). Each variable name s will occur at most once in each pattern.
• ConstantP 42 matches only Constant 42 and produces an empty list of bindings. It works in the same way for the rest of the integer numbers.
• PairP [a1, a2] matches expression Pair [b1, b2] if a1 matches b1 and a2 matches b2. The matching produces a concatenated list of both matches.
• ListP ps matches an expression List xs, if every value from xs matches the corresponding pattern in ps. The match produces a list we get by concatenating the bindings received by all of the matchings.
• OperatorP (a, x) matches expression Operator(b, y), if the names of the operators a and b are the same and "x" matches "y". The matching produces a list of binding we get by matching x and y.

If you could give me some tips in which direction to go, i think that my function should be something like this I guess, but not sure hot to cover all cases recursively

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

Answer 1

Use more pattern matching.
Then you go through the list of rules one by one and translate them, recursing when the rule depends on a sub-match.
You only need to define the cases of matching constructors, leaving the mismatches for the last, default, case.

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 

but you can make things more convenient by defining some helper functions.
(The Pair clause above gets unwieldy once you type all of it in.)

For example, concatenating two optional lists only if neither is NONE can be written very concisely as a function:

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

and lets you write a single line

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

and that function may come in handy in other situations as well.
(The list rules are painful, if not impossible, to write without helper functions.)

A more elaborated example:

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 

Test:

- 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