## Tuple matching

Here is an algorithm that can be used to match tuples. For example, on matching (a, b, (c, d)) against (1, 2, (3, 4)) we'd hope to get the set (a = 1, b = 2, c = 3, d = 4).
module type S = sig

type expr =
| E_var of string
| E_const of int
| E_tuple of expr list

val const : int -> expr
val var : string -> expr
val tuple : expr list -> expr

val tuple_match : (string * expr) list -> expr -> expr -> (string * expr) list
val tuple_of_expr : expr -> expr

end

module Expr : S =
struct

type expr =
| E_var of string
| E_const of int
| E_tuple of expr list

let var s = E_var s
let const i = E_const i
let tuple t = E_tuple t

let as_tuple = function
| E_tuple l as t -> t
| _ ->  failwith "Tuple expected"

let rec tuple_match acc x y =
match x with
| E_var (s) -> (s, y)::acc
| E_tuple ((h::t)) ->
let (E_tuple l) = as_tuple y in
let acc = tuple_match acc (tuple t) (tuple (List.tl l)) in
tuple_match acc h (List.hd l)
| E_tuple [] -> acc
| _ as unk -> failwith "Match failure"

end

For example,
(* (a, b, t) |- (1, 2, (3, 4)) *)
let x = Expr.tuple
[Expr.var "a"; Expr.var "b"; Expr.var "t" ] in
let y = Expr.tuple [Expr.const 1; Expr.const 2;
Expr.tuple [Expr.const 3; Expr. const 4] ] in
Expr.tuple_match [] x y
;;

in the top-level prints
- : (string * Expr.expr) list =
[("a", Expr.E_const 1); ("b", Expr.E_const 2);
("t", Expr.E_tuple [Expr.E_const 3; Expr.E_const 4])]

whereas
(* (a, b, (c, d)) |- (1, 2, (3, 4))*)
let x = Expr.tuple
[Expr.var "a"; Expr.var "b";
Expr.tuple [Expr.var "c"; Expr.var "d"]] in
let y = Expr.tuple
[Expr.const 1; Expr.const 2;
Expr.tuple [Expr.const 3; Expr. const 4]] in
Expr.tuple_match [] x y
;;

results in this
- : (string * Expr.expr) list =
[("a", Expr.E_const 1); ("b", Expr.E_const 2); ("c", Expr.E_const 3);
("d", Expr.E_const 4)]