type tree = Leaf of int
| Fork of tree * tree
let tree = Fork (Leaf 1,
(Fork (Leaf 4,
Leaf 7)))
type cxt = Top
| L of cxt * tree
| R of tree * cxt
type loc = tree * cxt
(* Location manipulation functions *)
let left (t, c) = match t with Fork (l, r) -> (l, L (c, r))
let right (t, c) = match t with Fork (l, r) -> (r, R (l, c))
let parent (t, c) = match c with
(L (c, r)) -> (Fork (t, r), c)
| (R (l, c)) -> (Fork (l, t), c)
let zip t = (t, Top)
let value (t, c) = t
let isRoot (t, c) = match c with Top -> true
| _ -> false
(* Implementation of attributes *)
let rec smin l = match (value l) with
Leaf v -> v
| _ -> min (smin (left l)) (smin (right l))
let rec ival l = if (isRoot l)
then (smin l) else ival (parent l)
let rec sres l = match (value l) with
Leaf _ -> Leaf (ival l)
| _ -> Fork (sres (left l), sres (right l))
let transform t = sres (zip t)