Tuple matching

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)]