The remaining problems use these type definitions, which are inspired by the type definitions OCamls implementation would use to implement pattern matching:

type pattern = WildcardP | VariableP of string | UnitP | ConstantP of int | ConstructorP of string * pattern | TupleP of pattern list

type valu = Constant of int | Unit | Constructor of string * valu | Tuple of valu list

Given valu v and pattern p, either p matches v or not. If it does, the match produces a list of string * valu pairs; order in the list does not matter. The rules for matching should be unsurprising:

WildcardP matches everything and produces the empty list of bindings.

VariableP s matches any value v and produces the one-element list holding (s,v).

UnitP matches only Unit and produces the empty list of bindings.

ConstantP 17 matches only Constant 17 and produces the empty list of bindings (and similarly for other integers).

ConstructorP(s1,p) matches Constructor(s2,v) if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name.

TupleP ps matches a value of the form Tuple vs if ps and vs have the same length and for all i, the i th element of ps matches the i th element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together. Nothing else matches.

10. Write a function check_pat that takes a pattern and returns true if and only if all the variables appearing in the pattern are distinct from each other (i.e., use different strings). The constructor names are not relevant. Hints: The sample solution uses two helper functions. The first takes a pattern and returns a list of all the strings it uses for variables. Using List.fold_left with a function that uses @ is useful in one case. The second takes a list of strings and decides if it has repeats. List.exists or List.mem may be useful. Sample solution is 15 lines. These are hints: We are not requiring List.fold_left and List.exists/List.mem here, but they make it easier.

11. Write a function matches of type valu -> pattern -> (string * valu) list option. It should take a value and a pattern, and return Some lst where lst is the list of bindings if the value matches the pattern, or None otherwise. Note that if the value matches but the pattern has no variables in it (i.e., no patterns of the form VariableP s), then the result is Some []. Hints: Sample solution has one match expression with 7 branches. The branch for tuples uses all_answers and List.combine. Sample solution is about 18 lines. Remember to look above for the rules for what patterns match what values, and what bindings they produce.

12. Write a function first_match of type valu -> pattern list -> (string * valu) list option. It returns None if no pattern in the list matches or Some lst where lst is the list of bindings for the first pattern in the list that matches. Hints: Use first_answer and a try-with-expression. Sample solution is about 3 lines.