Documentation

Linglib.Core.Data.RoseTree.ReplaceAt

Replacement at an address of a rose tree #

RoseTree.replaceAt puts a tree in place of the subtree at a Gorn address. The subtree at an address neither above nor below the replaced one is unchanged, the subtree at an address above it has the replacement made inside it, and the replacement trades the nodes of the old subtree for those of the new. Its effect on the frontier is in RoseTree/Span.lean.

def RoseTree.replaceAt {α : Type u_1} :
RoseTree α → List ℕ → RoseTree α → RoseTree α

Replace the subtree at a Gorn address; an address outside the tree leaves it unchanged.

Equations
Instances For
    @[simp]
    theorem RoseTree.replaceAt_nil {α : Type u_1} (t new : RoseTree α) :
    t.replaceAt [] new = new
    theorem RoseTree.replaceAt_cons {α : Type u_1} (a : α) (cs : List (RoseTree α)) (i : ℕ) (p : List ℕ) (new : RoseTree α) :
    (node a cs).replaceAt (i :: p) new = node a (cs.modify i fun (x : RoseTree α) => x.replaceAt p new)
    @[simp]
    theorem RoseTree.children_replaceAt_cons {α : Type u_1} (t : RoseTree α) (i : ℕ) (p : List ℕ) (new : RoseTree α) :
    (t.replaceAt (i :: p) new).children = t.children.modify i fun (x : RoseTree α) => x.replaceAt p new
    @[simp]
    theorem RoseTree.value_replaceAt_cons {α : Type u_1} (t : RoseTree α) (i : ℕ) (p : List ℕ) (new : RoseTree α) :
    (t.replaceAt (i :: p) new).value = t.value
    theorem RoseTree.value_replaceAt {α : Type u_1} {t s : RoseTree α} {p : List ℕ} (h : t[p]? = some s) {new : RoseTree α} (hv : new.value = s.value) :
    (t.replaceAt p new).value = t.value
    theorem RoseTree.replaceAt_cons_of_getElem? {α : Type u_1} {t c : RoseTree α} {i : ℕ} (hc : t.children[i]? = some c) (p : List ℕ) (new : RoseTree α) :
    t.replaceAt (i :: p) new = node t.value (t.children.set i (c.replaceAt p new))
    theorem RoseTree.getElem?_replaceAt_of_not_prefix {α : Type u_1} {t new : RoseTree α} {p q : List ℕ} (hpq : ¬p <+: q) (hqp : ¬q <+: p) :
    (t.replaceAt p new)[q]? = t[q]?

    Away from the replaced address, at an address neither above nor below it, the subtree is unchanged.

    theorem RoseTree.getElem?_replaceAt_of_prefix {α : Type u_1} {t new : RoseTree α} {p q : List ℕ} (hqp : q <+: p) :
    (t.replaceAt p new)[q]? = Option.map (fun (x : RoseTree α) => x.replaceAt (List.drop q.length p) new) t[q]?

    At an address above the replaced one, the subtree has the replacement inside it.

    theorem RoseTree.getElem?_replaceAt_append {α : Type u_1} {t new : RoseTree α} {p : List ℕ} (hp : t[p]?.isSome = true) (q : List ℕ) :
    (t.replaceAt p new)[p ++ q]? = new[q]?
    theorem RoseTree.numNodes_replaceAt {α : Type u_1} {t s : RoseTree α} {p : List ℕ} (h : t[p]? = some s) (new : RoseTree α) :
    (t.replaceAt p new).numNodes + s.numNodes = t.numNodes + new.numNodes

    Replacing the subtree s at an address by new trades the nodes of s for those of new.

    theorem RoseTree.numNodes_replaceAt_lt {α : Type u_1} {t s : RoseTree α} {p : List ℕ} (h : t[p]? = some s) {new : RoseTree α} (hlt : new.numNodes < s.numNodes) :

    Replacing a subtree by a strictly smaller one shrinks the tree.