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