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 WAA28793; Mon, 9 Jun 2003 22:18:44 +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 WAA28693 for <caml-list@pauillac.inria.fr>; Mon, 9 Jun 2003 22:18:43 +0200 (MET DST)
X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com
Received: from alfa.fastwebnet.it (relay-3.fastweb.it [213.140.2.42] (may be forged))
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h59KIgT13413
	for <caml-list@inria.fr>; Mon, 9 Jun 2003 22:18:42 +0200 (MET DST)
Received: from inferi (23.251.77.99) by alfa.fastwebnet.it (6.7.016)
        id 3ED29E9B00205482 for caml-list@inria.fr; Mon, 9 Jun 2003 22:18:42 +0200
Date: Mon, 9 Jun 2003 22:21:25 +0200
From: Mattia Dongili <dongili@supereva.it>
To: caml-list@inria.fr
Subject: [Caml-list] newbie nary tree problem
Message-Id: <20030609222125.0c2cb1c8.dongili@supereva.it>
X-Mailer: Sylpheed version 0.7.4 (GTK+ 1.2.10; i386-debian-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; supereva:99 newbie:01 pointers:01 const:01 subst:01 foreach:01 val:01 caml-list:01 passing:01 recursion:01 caml:01 int:01 rec:01 match:02 her:97 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

Hello,

1. I'm new to this list, so forgive me if I'm asking in the wrong place
   (well... and please supply pointers to the right resources)
2. Sorry, this mail is quite long

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;;

eg:
let tt1 = Term("f", [Var "x"; Var "y"]);;
let tt2 = Term("f", [Term("h", [Var "z"]); Term("g",[Var "y"]) ]);;

tt1 and tt2 represent f(x,y) and f( h(z), g(y) ) respectively

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>

so launching
# matchterm (tt1,tt2);;

I'd expect
- : Subst [("x", Term("h", [Var "z"]); ("y", Term("g",[Var "y"]))]

I'm at the very beginning as caml programmer so I' trying to go ahead
step by step. My first attempt is to create the list of matches so I'm
implementing something as follows:

let rec matchtermlist = function       
        ( Var v1 , x ) ->  [(v1, x)]
    |   ( Term (t1, l1), Term (t2, l2)) ->

            let rec foreach f lst tt =
                match lst with
                    [] -> []
                |   tt1 :: ll1 -> f(tt1,tt) :: foreach (f) ll1 tt
(* val foreach : ('a * 'b -> 'c) -> 'a list -> 'b -> 'c list = <fun> *)
            in
            foreach (matchtermlist) l2 (Term(t1, l1))

    |   ( _, _) -> []
;;

this generates an obvious error regarding the return value in the second
match:

This expression has type (string * term) list list but is here used with
type  (string * term) list

Reading old messages in the caml-list I thought that passing a reference
of a list to fill during recursion could be a good idea but I'm not
having much success...

Can anybody advise a better way to proceed? I'm not looking for the
solution, I'm trying to understand to right way(R) to think in caml.

thanks a lot to anybody who'll spend some time over this mail :)

-- 
mattia

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