module M = Map.Make(String)

type term = V of string
          | F of string * term list

(* da substitutia unui termen, substituind pana la capat in subtermeni
 * daca dictionarul are x -> f(y), z -> g(x, a)
 * substitutia lui h(x, f(z))  e  h(f(y), f(g(f(y), a))) *)
                               
let find m =        (* dictionarul m e acelasi la fiecare apel *)
  let rec find1 = function        
    (* daca v are substitutie, continua cu aceasta, altfel ramane V v *)
    | V v -> (try find1 (M.find v m) with Not_found -> V v)
    | F (f, tl) -> F(f, List.map find1 tl)        (* aplica fiecarui subtermen *)
  in find1

let occurs x =                (* parametrul x e acelasi la fiecare apel *)
  let rec occur1 = function        (* apare x in termenul t ? *)
  | V v -> v = x                (* acelasi nume *)
  | F (_, tl) -> List.exists occur1 tl
  in occur1
                             
let rec union m t1 t2 = (* returneaza un nou dictionar *)
  match (find m t1, find m t2) with
  | (V x, t) | (t, V x) -> if t = V x then m
                           else if occurs x t then failwith "substitutie circulara"
                           else M.add x t m
  | (F (f1, arg1), F (f2, arg2)) -> if f1 <> f2 then failwith "functii diferite"
                                    else List.fold_left2 union m arg1 arg2  (* parcurge 2 liste *)
;;
let m = M.singleton "x" (F ("f", [V "y"]))
;;
let m1 = union m (V "z") (F ("g", [V "x"; F ("a", [])]))
;;
find m1 (F("h", [V "x"; F("f",[V "z"])]))

This document was generated using caml2html