Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] newbie nary tree problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Mattia Dongili <dongili@s...>
Subject: [Caml-list] newbie nary tree problem

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

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> *)
            foreach (matchtermlist) l2 (Term(t1, l1))

    |   ( _, _) -> []

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

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


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: