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.
Replace the subtree at a Gorn address; an address outside the tree leaves it unchanged.
Equations
- x✝¹.replaceAt [] x✝ = x✝
- (RoseTree.node a cs).replaceAt (i :: p) x✝ = RoseTree.node a (cs.modify i fun (x : RoseTree α) => x.replaceAt p x✝)
Instances For
@[simp]
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)
:
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]?