Re: [Caml-list] newbie nary tree problem

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

 > Her comes my problem: I need to implement some kind of pattern matching
 > in an nary tree structure with as follow
 > 
 > type term = Const of int | Var of string | Term of string * term list;;
 > 
 > type matchres = NoMatch | Subst of (string * term) list;;
 > 
 > type matchres represent a substitution list in a successful pattern
 > matching, I need to implement this pattern matching as follows:
 > 
 > matchterm :  term * term -> matchres = <fun>

I couldn't find out the precise  meaning of your code, but if you want
to implement  matching (that is  *not* unification), here is  a simple
way to do it:

======================================================================
module Subst = Map.Make(String)
exception NoMatch

let rec match_term s = function
  | Const n1, Const n2 when n1 = n2 -> 
      s
  | Var v1,   t2 ->
      (try if Subst.find v1 s = t2 then s else raise NoMatch
       with Not_found -> Subst.add v1 t2 s)
  | Term (f1, l1), Term (f2, l2) when f1 = f2 ->
      match_terms s (l1, l2)
  | _ -> 
      raise NoMatch

and match_terms s = function
  | [], [] ->
      s
  | t1 :: l1, t2 :: l2 ->
      match_terms (match_term s (t1, t2)) (l1, l2)
  | _ ->
      raise NoMatch

let matching t1 t2 = match_term Subst.empty (t1, t2)
======================================================================

Notice the use of an exception  NoMatch instead of a sum type, and the
use of Ocaml's maps instead of association lists.

Hope this helps,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners