Union-find with union by rank and full path compression: determinism and call-to-run facts
DefinitionAlgo_union_find_FactsGenerated execution facts for union_find.algo, including the relation between a reusable Call witness and any completed Run of the same inputs. The determinism bridge lets ordinary-output and cost corollaries reuse the constructive call theorem without repeating its algorithm analysis.
This bundle depends on the stable algorithm definition and the corresponding facts for imported components. It does not introduce a separate specification of what the program computes.
<!-- algo2lean-provenance-v0.1.4 -->Algo2Lean provenance and reproduction. These definitions target Algo2Lean v0.1.4, using the compiler source at public commit 0f79d5e4242e6477531c9ee4410409f5b1c92f76, and Lean 4.33.1. The versioned compiler location is Algo2Lean v0.1.4. Compile all supplied .algo files and imports to reproduce the raw generated definitions. Release publication and exact website parity require their separately recorded checks; this metadata alone does not assert them. Prove2Me imports and declaration packaging are mechanically adapted, with original hashes, compiler-reported source ranges, and adaptations recorded in transplant provenance. Exact reproduction does not prove the compiler correct.
import Definitions.Def_Algo_union_find_Generated
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
-- Generated by Algo2Lean 0.1.4 https://github.com/lunjiah/algo2lean
-- Optional proof certificate; execution remains the generated Step relation.
namespace «Algo».«union_find»
open Algo2LeanCore _root_.Algo2LeanGenerated
namespace Algo2LeanGenerated
private def next_UnionFind___init__ (h : Heap) (s : State_UnionFind___init__) (stack : Stack) : Nat → Configuration
| 1 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind___init__ (s.t3)) stack)
| 2 => (.active h (Frame.fn_UnionFind___init__ 1 { s with t3 := () }) stack)
| 3 => if s.t4 then (.active h (Frame.fn_UnionFind___init__ 7 s) stack) else (.active h (Frame.fn_UnionFind___init__ 2 s) stack)
| 4 => (.active h (Frame.fn_UnionFind___init__ 3 { s with t4 := (decide ((s.v2 < s.v1))) }) stack)
| 5 => (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
| 6 => (.active h (Frame.fn_UnionFind___init__ 5 { s with v2 := (s.v2 + (1 : Int)) }) stack)
| 7 => (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v2 s.v2) (Frame.fn_UnionFind___init__ 6 s) stack)
| 8 => (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
| 9 => (.active h (Frame.fn_UnionFind___init__ 8 { s with v2 := (0 : Int) }) stack)
| 10 => (.active (set_UnionFind_size h (s.v0) (s.v1)) (Frame.fn_UnionFind___init__ 9 s) stack)
| 11 => (.active (set_UnionFind_rank h (s.t6) (s.t5)) (Frame.fn_UnionFind___init__ 10 s) stack)
| 12 => (.active h (Frame.fn_UnionFind___init__ 11 { s with t6 := s.v0 }) stack)
| 13 => (.active (h.allocate (fun _ => s.t7)) (Frame.fn_UnionFind___init__ 12 { s with t5 := h.nextRef }) stack)
| 14 => (.active h (Frame.fn_UnionFind___init__ 13 { s with t7 := (0 : Int) }) stack)
| 15 => (.active (set_UnionFind_parent h (s.t9) (s.t8)) (Frame.fn_UnionFind___init__ 14 s) stack)
| 16 => (.active h (Frame.fn_UnionFind___init__ 15 { s with t9 := s.v0 }) stack)
| 17 => (.active (h.allocate (fun _ => s.t10)) (Frame.fn_UnionFind___init__ 16 { s with t8 := h.nextRef }) stack)
| 18 => (.active h (Frame.fn_UnionFind___init__ 17 { s with t10 := (0 : Int) }) stack)
| pc => .active h (.fn_UnionFind___init__ pc s) stack
private def next_UnionFind_find (h : Heap) (s : State_UnionFind_find) (stack : Stack) : Nat → Configuration
| 1 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t4)) stack)
| 2 => (.active h (Frame.fn_UnionFind_find 1 { s with t4 := s.v3 }) stack)
| 3 => (.active (h.tick "uf_compress" 1) (Frame.fn_UnionFind_find 2 s) stack)
| 4 => (.active (h.write s.v2 s.v1 s.v3) (Frame.fn_UnionFind_find 3 s) stack)
| 5 => (.active h (Frame.fn_UnionFind_find 4 { s with v3 := s.t5 }) stack)
| 6 => (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t6), v1 := s.t7 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_find 5 { s with t5 := result }) | _ => .invalid) :: stack))
| 7 => (.active h (Frame.fn_UnionFind_find 6 { s with t7 := (h.read s.v2 s.v1) }) stack)
| 8 => (.active h (Frame.fn_UnionFind_find 7 { s with t6 := s.t6 }) stack)
| 9 => (.active h (Frame.fn_UnionFind_find 8 { s with t6 := s.v0 }) stack)
| 10 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t9)) stack)
| 11 => (.active h (Frame.fn_UnionFind_find 10 { s with t9 := s.v1 }) stack)
| 12 => if s.t8 then (.active h (Frame.fn_UnionFind_find 11 s) stack) else (.active h (Frame.fn_UnionFind_find 9 s) stack)
| 13 => (.active h (Frame.fn_UnionFind_find 12 { s with t8 := (decide (((h.read s.v2 s.v1) = s.v1))) }) stack)
| 14 => (.active (h.tick "uf_find" 1) (Frame.fn_UnionFind_find 13 s) stack)
| 15 => (.active h (Frame.fn_UnionFind_find 14 { s with v2 := ((field_UnionFind_parent h (s.v0)).getD 0) }) stack)
| pc => .active h (.fn_UnionFind_find pc s) stack
private def next_UnionFind_union (h : Heap) (s : State_UnionFind_union) (stack : Stack) : Nat → Configuration
| 1 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t5)) stack)
| 2 => (.active h (Frame.fn_UnionFind_union 1 { s with t5 := true }) stack)
| 3 => (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v3 s.v4) (Frame.fn_UnionFind_union 2 s) stack)
| 4 => (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 2 s) stack)
| 5 => (.active (h.write ((field_UnionFind_rank h (s.v0)).getD 0) s.v3 ((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3) + (1 : Int))) (Frame.fn_UnionFind_union 2 s) stack)
| 6 => (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 5 s) stack)
| 7 => if s.t7 then (.active h (Frame.fn_UnionFind_union 4 s) stack) else (.active h (Frame.fn_UnionFind_union 6 s) stack)
| 8 => (.active h (Frame.fn_UnionFind_union 7 { s with t7 := (decide (((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v4) < (h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3)))) }) stack)
| 9 => if s.t6 then (.active h (Frame.fn_UnionFind_union 3 s) stack) else (.active h (Frame.fn_UnionFind_union 8 s) stack)
| 10 => (.active h (Frame.fn_UnionFind_union 9 { s with t6 := (decide (((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3) < (h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v4)))) }) stack)
| 11 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t9)) stack)
| 12 => (.active h (Frame.fn_UnionFind_union 11 { s with t9 := false }) stack)
| 13 => if s.t8 then (.active h (Frame.fn_UnionFind_union 12 s) stack) else (.active h (Frame.fn_UnionFind_union 10 s) stack)
| 14 => (.active h (Frame.fn_UnionFind_union 13 { s with t8 := (decide ((s.v3 = s.v4))) }) stack)
| 15 => (.active (h.tick "uf_union" 1) (Frame.fn_UnionFind_union 14 s) stack)
| 16 => (.active h (Frame.fn_UnionFind_union 15 { s with v4 := s.t10 }) stack)
| 17 => (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t11), v1 := s.t12 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_union 16 { s with t10 := result }) | _ => .invalid) :: stack))
| 18 => (.active h (Frame.fn_UnionFind_union 17 { s with t12 := s.v2 }) stack)
| 19 => (.active h (Frame.fn_UnionFind_union 18 { s with t11 := s.t11 }) stack)
| 20 => (.active h (Frame.fn_UnionFind_union 19 { s with t11 := s.v0 }) stack)
| 21 => (.active h (Frame.fn_UnionFind_union 20 { s with v3 := s.t13 }) stack)
| 22 => (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t14), v1 := s.t15 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_union 21 { s with t13 := result }) | _ => .invalid) :: stack))
| 23 => (.active h (Frame.fn_UnionFind_union 22 { s with t15 := s.v1 }) stack)
| 24 => (.active h (Frame.fn_UnionFind_union 23 { s with t14 := s.t14 }) stack)
| 25 => (.active h (Frame.fn_UnionFind_union 24 { s with t14 := s.v0 }) stack)
| pc => .active h (.fn_UnionFind_union pc s) stack
private def next_UnionFind (h : Heap) (s : State_UnionFind) (stack : Stack) : Nat → Configuration
| 1 => (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind (s.t2)) stack)
| 2 => (.active h (Frame.fn_UnionFind 1 { s with t2 := s.v1 }) stack)
| 3 => (.active h (Frame.fn_UnionFind___init__ 18 ({ v0 := s.t4, v1 := s.t5 } : State_UnionFind___init__)) ((fun value => match value with | .fn_UnionFind___init__ result => (Frame.fn_UnionFind 2 { s with t3 := result }) | _ => .invalid) :: stack))
| 4 => (.active h (Frame.fn_UnionFind 3 { s with t5 := s.v0 }) stack)
| 5 => (.active h (Frame.fn_UnionFind 4 { s with t4 := s.v1 }) stack)
| 6 => (.active h (Frame.fn_UnionFind 5 { s with v1 := s.t6 }) stack)
| 7 => (.active (h.allocateObject "union_find.UnionFind") (Frame.fn_UnionFind 6 { s with t6 := h.nextObject }) stack)
| pc => .active h (.fn_UnionFind pc s) stack
/-- A total projection used only to certify uniqueness of actual transitions. -/
def next : Configuration → Configuration
| .done h result => .done h result
| .active h frame stack => match frame with
| .invalid => .active h .invalid stack
| .fn_UnionFind___init__ pc s => next_UnionFind___init__ h s stack pc
| .fn_UnionFind_find pc s => next_UnionFind_find h s stack pc
| .fn_UnionFind_union pc s => next_UnionFind_union h s stack pc
| .fn_UnionFind pc s => next_UnionFind h s stack pc
/-- Each generated rule agrees with the projection; guards remain in Step. -/
theorem step_next {before after : Configuration} (transition : Step before after) :
next before = after := by
cases transition with
| UnionFind___init___pc1 h s stack => rfl
| UnionFind___init___pc2 h s stack => rfl
| UnionFind___init___pc3_true h s stack condition => simp [next, next_UnionFind___init__, condition]
| UnionFind___init___pc3_false h s stack condition => simp [next, next_UnionFind___init__, condition]
| UnionFind___init___pc4 h s stack => rfl
| UnionFind___init___pc5 h s stack => rfl
| UnionFind___init___pc6 h s stack => rfl
| UnionFind___init___pc7 h s stack defined => rfl
| UnionFind___init___pc8 h s stack => rfl
| UnionFind___init___pc9 h s stack => rfl
| UnionFind___init___pc10 h s stack defined => rfl
| UnionFind___init___pc11 h s stack defined => rfl
| UnionFind___init___pc12 h s stack => rfl
| UnionFind___init___pc13 h s stack => rfl
| UnionFind___init___pc14 h s stack => rfl
| UnionFind___init___pc15 h s stack defined => rfl
| UnionFind___init___pc16 h s stack => rfl
| UnionFind___init___pc17 h s stack => rfl
| UnionFind___init___pc18 h s stack => rfl
| UnionFind_find_pc1 h s stack => rfl
| UnionFind_find_pc2 h s stack => rfl
| UnionFind_find_pc3 h s stack => rfl
| UnionFind_find_pc4 h s stack defined => rfl
| UnionFind_find_pc5 h s stack => rfl
| UnionFind_find_pc6 h s stack => rfl
| UnionFind_find_pc7 h s stack defined => rfl
| UnionFind_find_pc8 h s stack defined => rfl
| UnionFind_find_pc9 h s stack => rfl
| UnionFind_find_pc10 h s stack => rfl
| UnionFind_find_pc11 h s stack => rfl
| UnionFind_find_pc12_true h s stack condition => simp [next, next_UnionFind_find, condition]
| UnionFind_find_pc12_false h s stack condition => simp [next, next_UnionFind_find, condition]
| UnionFind_find_pc13 h s stack defined => rfl
| UnionFind_find_pc14 h s stack => rfl
| UnionFind_find_pc15 h s stack defined => rfl
| UnionFind_union_pc1 h s stack => rfl
| UnionFind_union_pc2 h s stack => rfl
| UnionFind_union_pc3 h s stack defined => rfl
| UnionFind_union_pc4 h s stack defined => rfl
| UnionFind_union_pc5 h s stack defined => rfl
| UnionFind_union_pc6 h s stack defined => rfl
| UnionFind_union_pc7_true h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc7_false h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc8 h s stack defined => rfl
| UnionFind_union_pc9_true h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc9_false h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc10 h s stack defined => rfl
| UnionFind_union_pc11 h s stack => rfl
| UnionFind_union_pc12 h s stack => rfl
| UnionFind_union_pc13_true h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc13_false h s stack condition => simp [next, next_UnionFind_union, condition]
| UnionFind_union_pc14 h s stack => rfl
| UnionFind_union_pc15 h s stack => rfl
| UnionFind_union_pc16 h s stack => rfl
| UnionFind_union_pc17 h s stack => rfl
| UnionFind_union_pc18 h s stack => rfl
| UnionFind_union_pc19 h s stack defined => rfl
| UnionFind_union_pc20 h s stack => rfl
| UnionFind_union_pc21 h s stack => rfl
| UnionFind_union_pc22 h s stack => rfl
| UnionFind_union_pc23 h s stack => rfl
| UnionFind_union_pc24 h s stack defined => rfl
| UnionFind_union_pc25 h s stack => rfl
| UnionFind_pc1 h s stack defined => rfl
| UnionFind_pc2 h s stack => rfl
| UnionFind_pc3 h s stack => rfl
| UnionFind_pc4 h s stack => rfl
| UnionFind_pc5 h s stack => rfl
| UnionFind_pc6 h s stack => rfl
| UnionFind_pc7 h s stack => rfl
/-- Imported determinism composes without reopening imported transition rules. -/
theorem deterministic : Deterministic Step := by
intro before left right first second
exact (step_next first).symm.trans (step_next second)
end Algo2LeanGenerated
end «Algo».«union_find»
namespace Algo.«union_find»
open Algo2LeanCore _root_.Algo2LeanGenerated Algo2LeanGenerated
theorem UnionFind.__init__.Run.eq_of_call {before after expectedHeap input output expected}
(run : _root_.Algo.«union_find».UnionFind.__init__.Run before input after output)
(call : _root_.Algo.«union_find».UnionFind.__init__.Call before input expectedHeap expected) :
after = expectedHeap ∧ output = expected := by
have same := Reaches.eq_of_terminal (step := Step) deterministic
run.2 call.2.root (terminal _ _) (terminal _ _)
cases same
exact ⟨rfl, rfl⟩
theorem UnionFind.find.Run.eq_of_call {before after expectedHeap input output expected}
(run : _root_.Algo.«union_find».UnionFind.find.Run before input after output)
(call : _root_.Algo.«union_find».UnionFind.find.Call before input expectedHeap expected) :
after = expectedHeap ∧ output = expected := by
have same := Reaches.eq_of_terminal (step := Step) deterministic
run.2 call.2.root (terminal _ _) (terminal _ _)
cases same
exact ⟨rfl, rfl⟩
theorem UnionFind.union.Run.eq_of_call {before after expectedHeap input output expected}
(run : _root_.Algo.«union_find».UnionFind.union.Run before input after output)
(call : _root_.Algo.«union_find».UnionFind.union.Call before input expectedHeap expected) :
after = expectedHeap ∧ output = expected := by
have same := Reaches.eq_of_terminal (step := Step) deterministic
run.2 call.2.root (terminal _ _) (terminal _ _)
cases same
exact ⟨rfl, rfl⟩
theorem UnionFind.Run.eq_of_call {before after expectedHeap input output expected}
(run : _root_.Algo.«union_find».UnionFind.Run before input after output)
(call : _root_.Algo.«union_find».UnionFind.Call before input expectedHeap expected) :
after = expectedHeap ∧ output = expected := by
have same := Reaches.eq_of_terminal (step := Step) deterministic
run.2 call.2.root (terminal _ _) (terminal _ _)
cases same
exact ⟨rfl, rfl⟩
end Algo.«union_find»