From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA19250; Fri, 13 Jun 2003 12:51:01 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA19867 for <caml-list@pauillac.inria.fr>; Fri, 13 Jun 2003 12:50:59 +0200 (MET DST)
Received: from lri.lri.fr (lri.lri.fr [129.175.15.1])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5DAoxT19749
	for <caml-list@inria.fr>; Fri, 13 Jun 2003 12:50:59 +0200 (MET DST)
Received: from pc8-123 (pc8-123 [129.175.8.123])
          by lri.lri.fr (8.11.6p2/jtpda-5.3.2) with ESMTP id h5DAfbt22239
          ; Fri, 13 Jun 2003 12:41:37 +0200 (MEST)
Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian))
	id 19Qm01-0001UL-00; Fri, 13 Jun 2003 12:41:37 +0200
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Message-ID: <16105.43617.135822.74686@gargle.gargle.HOWL>
Date: Fri, 13 Jun 2003 12:41:37 +0200
To: Mattia Dongili <dongili@supereva.it>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] newbie nary tree problem
In-Reply-To: <20030609222125.0c2cb1c8.dongili@supereva.it>
References: <20030609222125.0c2cb1c8.dongili@supereva.it>
X-Mailer: VM 7.03 under Emacs 20.7.2
Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre)
X-MailScanner: Found to be clean
X-Spam: no; 0.00; filliatre:01 lri:01 caml-list:01 newbie:01 const:01 subst:01 unification:01 ocaml's:01 filliatr:01 int:01 rec:01 match:02 her:97 tree:02 exception:02 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk


 > 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