[Caml-list] newbie nary tree problem

[Caml-list] newbie nary tree problem

[Mattia Dongili]

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

Re: [Caml-list] newbie nary tree problem

[Jean-Christophe Filliatre]

 > 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