## 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" endFor 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)]