OCaml

The application of a substitution to a tree t, written (t ), is the simultaneous replacement of all variables vi occurring in t by the their tree/variable associations in . For example, with 1 defined as above, we would have:

v0 1 = v0 { (v0 -> (C -> C))/v1, (C -> v1)/v0 } = (C -> v1).

Write the function applySubstitutionToTree : subst -> t -> t such that a function call(applySubstitutionToTree subst t), produces the result of performing the substitution subst on tree t.

For example, in OCaml syntax, if we have

let t0 = Arrow { from = Var 0; too = Arrow { from = C; too = C }} let t1 = Arrow { from = C ; too = Var v1 } let s1 = [ {tree = t0; var = 1} ; {tree = t1; var = 0} ]

Then we should get

 # applySubstitutionToTree s1 t0;; - : t = Arrow {from = Arrow {from = C; too = Var 1}; too = Arrow {from = C; too = C}}