Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Union-find with union by rank and full path compression: generated algorithm definition

Definition
Algo_union_find_Generated

by lunjia · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsdata-structuresrunning-timetextbook

The compiled semantics of union_find.algo in the examples/kruskal import root. This bundle contains source-function frames, transition rules and the stable public call/run/output interfaces. Imported modules are linked through the shared execution semantics, including mutable aliases and named tick increments.

These are the algorithm definitions proved about by the corresponding analysis nodes. Named-line observations are in a separate Points bundle, so editing labels does not change the main algorithm statement. The reproduction target is Algo2Lean v0.1.4; raw generated files and platform-adapted packaging are tracked separately, and release/source links must be finalized before submission.

<!-- 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.

Definition code
import Definitions.Def_Algo2LeanLib_Modules

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

namespace Algo.«union_find»

open _root_.Algo2LeanGenerated

-- Independently compiled module; imported algorithms keep their own transitions.
namespace Algo2LeanGenerated

abbrev Ref_UnionFind := ObjectRef

-- Shallow class membership; fields and referenced objects are observed separately.
def is_UnionFind (h : Heap) (ref : Ref_UnionFind) : Prop :=
  ref < h.nextObject ∧ h.objectClass ref = some "union_find.UnionFind"
instance (h : Heap) (ref : Ref_UnionFind) : Decidable (is_UnionFind h ref) :=
  inferInstanceAs (Decidable (ref < h.nextObject ∧ h.objectClass ref = some "union_find.UnionFind"))

def field_UnionFind_parent (h : Heap) (ref : Ref_UnionFind) : Option SeqRef :=
  if is_UnionFind h ref then (h.readField ref "parent").bind ObjectValue.asSeq else none
def set_UnionFind_parent (h : Heap) (ref : Ref_UnionFind) (value : SeqRef) : Heap :=
  h.writeField ref "parent" (ObjectValue.seqValue value)
@[simp] theorem field_UnionFind_parent_set (h : Heap) (ref : Ref_UnionFind) (value : SeqRef)
    (valid : is_UnionFind h ref) :
    field_UnionFind_parent (set_UnionFind_parent h ref value) ref = some value := by
  have valid' : is_UnionFind (set_UnionFind_parent h ref value) ref := by
    simpa [set_UnionFind_parent, is_UnionFind] using valid
  rw [field_UnionFind_parent, if_pos valid']
  unfold set_UnionFind_parent
  rw [Heap.readField_writeField_same h ref "parent" _ "union_find.UnionFind" valid.2]
  rfl

def field_UnionFind_rank (h : Heap) (ref : Ref_UnionFind) : Option SeqRef :=
  if is_UnionFind h ref then (h.readField ref "rank").bind ObjectValue.asSeq else none
def set_UnionFind_rank (h : Heap) (ref : Ref_UnionFind) (value : SeqRef) : Heap :=
  h.writeField ref "rank" (ObjectValue.seqValue value)
@[simp] theorem field_UnionFind_rank_set (h : Heap) (ref : Ref_UnionFind) (value : SeqRef)
    (valid : is_UnionFind h ref) :
    field_UnionFind_rank (set_UnionFind_rank h ref value) ref = some value := by
  have valid' : is_UnionFind (set_UnionFind_rank h ref value) ref := by
    simpa [set_UnionFind_rank, is_UnionFind] using valid
  rw [field_UnionFind_rank, if_pos valid']
  unfold set_UnionFind_rank
  rw [Heap.readField_writeField_same h ref "rank" _ "union_find.UnionFind" valid.2]
  rfl

def field_UnionFind_size (h : Heap) (ref : Ref_UnionFind) : Option Int :=
  if is_UnionFind h ref then (h.readField ref "size").bind ObjectValue.asInt else none
def set_UnionFind_size (h : Heap) (ref : Ref_UnionFind) (value : Int) : Heap :=
  h.writeField ref "size" (ObjectValue.intValue value)
@[simp] theorem field_UnionFind_size_set (h : Heap) (ref : Ref_UnionFind) (value : Int)
    (valid : is_UnionFind h ref) :
    field_UnionFind_size (set_UnionFind_size h ref value) ref = some value := by
  have valid' : is_UnionFind (set_UnionFind_size h ref value) ref := by
    simpa [set_UnionFind_size, is_UnionFind] using valid
  rw [field_UnionFind_size, if_pos valid']
  unfold set_UnionFind_size
  rw [Heap.readField_writeField_same h ref "size" _ "union_find.UnionFind" valid.2]
  rfl

/-- Build input data directly; this helper does not execute `__init__`. -/
def create_UnionFind (h : Heap) (value_parent : SeqRef) (value_rank : SeqRef) (value_size : Int) : Heap × Ref_UnionFind :=
  let ref := h.nextObject
  let h := h.allocateObject "union_find.UnionFind"
  let h := set_UnionFind_parent h ref value_parent
  let h := set_UnionFind_rank h ref value_rank
  let h := set_UnionFind_size h ref value_size
  (h, ref)

structure State_UnionFind___init__ where
  v0 : Ref_UnionFind := 0 -- self
  v1 : Int := 0 -- size
  v2 : Int := 0 -- vertex
  t3 : Unit := () -- temporary
  t4 : Bool := false -- temporary
  t5 : SeqRef := 0 -- temporary
  t6 : Ref_UnionFind := 0 -- temporary
  t7 : Int := 0 -- temporary
  t8 : SeqRef := 0 -- temporary
  t9 : Ref_UnionFind := 0 -- temporary
  t10 : Int := 0 -- temporary

structure State_UnionFind_find where
  v0 : Ref_UnionFind := 0 -- self
  v1 : Int := 0 -- vertex
  v2 : SeqRef := 0 -- parent
  v3 : Int := 0 -- root
  t4 : Int := 0 -- temporary
  t5 : Int := 0 -- temporary
  t6 : Ref_UnionFind := 0 -- temporary
  t7 : Int := 0 -- temporary
  t8 : Bool := false -- temporary
  t9 : Int := 0 -- temporary

structure State_UnionFind_union where
  v0 : Ref_UnionFind := 0 -- self
  v1 : Int := 0 -- a
  v2 : Int := 0 -- b
  v3 : Int := 0 -- left
  v4 : Int := 0 -- right
  t5 : Bool := false -- temporary
  t6 : Bool := false -- temporary
  t7 : Bool := false -- temporary
  t8 : Bool := false -- temporary
  t9 : Bool := false -- temporary
  t10 : Int := 0 -- temporary
  t11 : Ref_UnionFind := 0 -- temporary
  t12 : Int := 0 -- temporary
  t13 : Int := 0 -- temporary
  t14 : Ref_UnionFind := 0 -- temporary
  t15 : Int := 0 -- temporary

structure State_UnionFind where
  v0 : Int := 0 -- size
  v1 : Ref_UnionFind := 0 -- _instance
  t2 : Ref_UnionFind := 0 -- temporary
  t3 : Unit := () -- temporary
  t4 : Ref_UnionFind := 0 -- temporary
  t5 : Int := 0 -- temporary
  t6 : Ref_UnionFind := 0 -- temporary

inductive Frame where
  | invalid
  | fn_UnionFind___init__ (pc : Nat) (state : State_UnionFind___init__)
  | fn_UnionFind_find (pc : Nat) (state : State_UnionFind_find)
  | fn_UnionFind_union (pc : Nat) (state : State_UnionFind_union)
  | fn_UnionFind (pc : Nat) (state : State_UnionFind)

inductive Result where
  | fn_UnionFind___init__ (value : Unit)
  | fn_UnionFind_find (value : Int)
  | fn_UnionFind_union (value : Bool)
  | fn_UnionFind (value : Ref_UnionFind)

abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)

inductive Step : Configuration → Configuration → Prop where
  | UnionFind___init___pc1 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind___init__ (s.t3)) stack)
  | UnionFind___init___pc2 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 2 s) stack) (.active h (Frame.fn_UnionFind___init__ 1 { s with t3 := () }) stack)
  | UnionFind___init___pc3_true (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (condition : s.t4 = true) :
      Step (.active h (Frame.fn_UnionFind___init__ 3 s) stack) (.active h (Frame.fn_UnionFind___init__ 7 s) stack)
  | UnionFind___init___pc3_false (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (condition : s.t4 = false) :
      Step (.active h (Frame.fn_UnionFind___init__ 3 s) stack) (.active h (Frame.fn_UnionFind___init__ 2 s) stack)
  | UnionFind___init___pc4 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 4 s) stack) (.active h (Frame.fn_UnionFind___init__ 3 { s with t4 := (decide ((s.v2 < s.v1))) }) stack)
  | UnionFind___init___pc5 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 5 s) stack) (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
  | UnionFind___init___pc6 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 6 s) stack) (.active h (Frame.fn_UnionFind___init__ 5 { s with v2 := (s.v2 + (1 : Int)) }) stack)
  | UnionFind___init___pc7 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind___init__ 7 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v2 s.v2) (Frame.fn_UnionFind___init__ 6 s) stack)
  | UnionFind___init___pc8 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 8 s) stack) (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
  | UnionFind___init___pc9 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 9 s) stack) (.active h (Frame.fn_UnionFind___init__ 8 { s with v2 := (0 : Int) }) stack)
  | UnionFind___init___pc10 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.v0))) :
      Step (.active h (Frame.fn_UnionFind___init__ 10 s) stack) (.active (set_UnionFind_size h (s.v0) (s.v1)) (Frame.fn_UnionFind___init__ 9 s) stack)
  | UnionFind___init___pc11 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.t6))) :
      Step (.active h (Frame.fn_UnionFind___init__ 11 s) stack) (.active (set_UnionFind_rank h (s.t6) (s.t5)) (Frame.fn_UnionFind___init__ 10 s) stack)
  | UnionFind___init___pc12 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 12 s) stack) (.active h (Frame.fn_UnionFind___init__ 11 { s with t6 := s.v0 }) stack)
  | UnionFind___init___pc13 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 13 s) stack) (.active (h.allocate (fun _ => s.t7)) (Frame.fn_UnionFind___init__ 12 { s with t5 := h.nextRef }) stack)
  | UnionFind___init___pc14 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 14 s) stack) (.active h (Frame.fn_UnionFind___init__ 13 { s with t7 := (0 : Int) }) stack)
  | UnionFind___init___pc15 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.t9))) :
      Step (.active h (Frame.fn_UnionFind___init__ 15 s) stack) (.active (set_UnionFind_parent h (s.t9) (s.t8)) (Frame.fn_UnionFind___init__ 14 s) stack)
  | UnionFind___init___pc16 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 16 s) stack) (.active h (Frame.fn_UnionFind___init__ 15 { s with t9 := s.v0 }) stack)
  | UnionFind___init___pc17 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 17 s) stack) (.active (h.allocate (fun _ => s.t10)) (Frame.fn_UnionFind___init__ 16 { s with t8 := h.nextRef }) stack)
  | UnionFind___init___pc18 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind___init__ 18 s) stack) (.active h (Frame.fn_UnionFind___init__ 17 { s with t10 := (0 : Int) }) stack)
  | UnionFind_find_pc1 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t4)) stack)
  | UnionFind_find_pc2 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 2 s) stack) (.active h (Frame.fn_UnionFind_find 1 { s with t4 := s.v3 }) stack)
  | UnionFind_find_pc3 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 3 s) stack) (.active (h.tick "uf_compress" 1) (Frame.fn_UnionFind_find 2 s) stack)
  | UnionFind_find_pc4 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : s.v2 < h.nextRef) :
      Step (.active h (Frame.fn_UnionFind_find 4 s) stack) (.active (h.write s.v2 s.v1 s.v3) (Frame.fn_UnionFind_find 3 s) stack)
  | UnionFind_find_pc5 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 5 s) stack) (.active h (Frame.fn_UnionFind_find 4 { s with v3 := s.t5 }) stack)
  | UnionFind_find_pc6 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 6 s) stack) (.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))
  | UnionFind_find_pc7 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (s.v2 < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind_find 7 s) stack) (.active h (Frame.fn_UnionFind_find 6 { s with t7 := (h.read s.v2 s.v1) }) stack)
  | UnionFind_find_pc8 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (is_UnionFind h (s.t6))) :
      Step (.active h (Frame.fn_UnionFind_find 8 s) stack) (.active h (Frame.fn_UnionFind_find 7 { s with t6 := s.t6 }) stack)
  | UnionFind_find_pc9 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 9 s) stack) (.active h (Frame.fn_UnionFind_find 8 { s with t6 := s.v0 }) stack)
  | UnionFind_find_pc10 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 10 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t9)) stack)
  | UnionFind_find_pc11 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 11 s) stack) (.active h (Frame.fn_UnionFind_find 10 { s with t9 := s.v1 }) stack)
  | UnionFind_find_pc12_true (h : Heap) (s : State_UnionFind_find) (stack : Stack) (condition : s.t8 = true) :
      Step (.active h (Frame.fn_UnionFind_find 12 s) stack) (.active h (Frame.fn_UnionFind_find 11 s) stack)
  | UnionFind_find_pc12_false (h : Heap) (s : State_UnionFind_find) (stack : Stack) (condition : s.t8 = false) :
      Step (.active h (Frame.fn_UnionFind_find 12 s) stack) (.active h (Frame.fn_UnionFind_find 9 s) stack)
  | UnionFind_find_pc13 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : ((s.v2 < h.nextRef))) :
      Step (.active h (Frame.fn_UnionFind_find 13 s) stack) (.active h (Frame.fn_UnionFind_find 12 { s with t8 := (decide (((h.read s.v2 s.v1) = s.v1))) }) stack)
  | UnionFind_find_pc14 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_find 14 s) stack) (.active (h.tick "uf_find" 1) (Frame.fn_UnionFind_find 13 s) stack)
  | UnionFind_find_pc15 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (((field_UnionFind_parent h (s.v0)).isSome = true))) :
      Step (.active h (Frame.fn_UnionFind_find 15 s) stack) (.active h (Frame.fn_UnionFind_find 14 { s with v2 := ((field_UnionFind_parent h (s.v0)).getD 0) }) stack)
  | UnionFind_union_pc1 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t5)) stack)
  | UnionFind_union_pc2 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 2 s) stack) (.active h (Frame.fn_UnionFind_union 1 { s with t5 := true }) stack)
  | UnionFind_union_pc3 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind_union 3 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v3 s.v4) (Frame.fn_UnionFind_union 2 s) stack)
  | UnionFind_union_pc4 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind_union 4 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 2 s) stack)
  | UnionFind_union_pc5 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) ∧ ((((field_UnionFind_rank h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind_union 5 s) stack) (.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)
  | UnionFind_union_pc6 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_UnionFind_union 6 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 5 s) stack)
  | UnionFind_union_pc7_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t7 = true) :
      Step (.active h (Frame.fn_UnionFind_union 7 s) stack) (.active h (Frame.fn_UnionFind_union 4 s) stack)
  | UnionFind_union_pc7_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t7 = false) :
      Step (.active h (Frame.fn_UnionFind_union 7 s) stack) (.active h (Frame.fn_UnionFind_union 6 s) stack)
  | UnionFind_union_pc8 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) :
      Step (.active h (Frame.fn_UnionFind_union 8 s) stack) (.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)
  | UnionFind_union_pc9_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t6 = true) :
      Step (.active h (Frame.fn_UnionFind_union 9 s) stack) (.active h (Frame.fn_UnionFind_union 3 s) stack)
  | UnionFind_union_pc9_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t6 = false) :
      Step (.active h (Frame.fn_UnionFind_union 9 s) stack) (.active h (Frame.fn_UnionFind_union 8 s) stack)
  | UnionFind_union_pc10 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) :
      Step (.active h (Frame.fn_UnionFind_union 10 s) stack) (.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)
  | UnionFind_union_pc11 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 11 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t9)) stack)
  | UnionFind_union_pc12 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 12 s) stack) (.active h (Frame.fn_UnionFind_union 11 { s with t9 := false }) stack)
  | UnionFind_union_pc13_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t8 = true) :
      Step (.active h (Frame.fn_UnionFind_union 13 s) stack) (.active h (Frame.fn_UnionFind_union 12 s) stack)
  | UnionFind_union_pc13_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t8 = false) :
      Step (.active h (Frame.fn_UnionFind_union 13 s) stack) (.active h (Frame.fn_UnionFind_union 10 s) stack)
  | UnionFind_union_pc14 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 14 s) stack) (.active h (Frame.fn_UnionFind_union 13 { s with t8 := (decide ((s.v3 = s.v4))) }) stack)
  | UnionFind_union_pc15 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 15 s) stack) (.active (h.tick "uf_union" 1) (Frame.fn_UnionFind_union 14 s) stack)
  | UnionFind_union_pc16 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 16 s) stack) (.active h (Frame.fn_UnionFind_union 15 { s with v4 := s.t10 }) stack)
  | UnionFind_union_pc17 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 17 s) stack) (.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))
  | UnionFind_union_pc18 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 18 s) stack) (.active h (Frame.fn_UnionFind_union 17 { s with t12 := s.v2 }) stack)
  | UnionFind_union_pc19 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (is_UnionFind h (s.t11))) :
      Step (.active h (Frame.fn_UnionFind_union 19 s) stack) (.active h (Frame.fn_UnionFind_union 18 { s with t11 := s.t11 }) stack)
  | UnionFind_union_pc20 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 20 s) stack) (.active h (Frame.fn_UnionFind_union 19 { s with t11 := s.v0 }) stack)
  | UnionFind_union_pc21 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 21 s) stack) (.active h (Frame.fn_UnionFind_union 20 { s with v3 := s.t13 }) stack)
  | UnionFind_union_pc22 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 22 s) stack) (.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))
  | UnionFind_union_pc23 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 23 s) stack) (.active h (Frame.fn_UnionFind_union 22 { s with t15 := s.v1 }) stack)
  | UnionFind_union_pc24 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (is_UnionFind h (s.t14))) :
      Step (.active h (Frame.fn_UnionFind_union 24 s) stack) (.active h (Frame.fn_UnionFind_union 23 { s with t14 := s.t14 }) stack)
  | UnionFind_union_pc25 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind_union 25 s) stack) (.active h (Frame.fn_UnionFind_union 24 { s with t14 := s.v0 }) stack)
  | UnionFind_pc1 (h : Heap) (s : State_UnionFind) (stack : Stack) (defined : is_UnionFind h s.t2) :
      Step (.active h (Frame.fn_UnionFind 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind (s.t2)) stack)
  | UnionFind_pc2 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 2 s) stack) (.active h (Frame.fn_UnionFind 1 { s with t2 := s.v1 }) stack)
  | UnionFind_pc3 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 3 s) stack) (.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))
  | UnionFind_pc4 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 4 s) stack) (.active h (Frame.fn_UnionFind 3 { s with t5 := s.v0 }) stack)
  | UnionFind_pc5 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 5 s) stack) (.active h (Frame.fn_UnionFind 4 { s with t4 := s.v1 }) stack)
  | UnionFind_pc6 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 6 s) stack) (.active h (Frame.fn_UnionFind 5 { s with v1 := s.t6 }) stack)
  | UnionFind_pc7 (h : Heap) (s : State_UnionFind) (stack : Stack) :
      Step (.active h (Frame.fn_UnionFind 7 s) stack) (.active (h.allocateObject "union_find.UnionFind") (Frame.fn_UnionFind 6 { s with t6 := h.nextObject }) stack)

theorem terminal (h : Heap) (result : Result) :
    Algo2LeanCore.Terminal Step (.done h result) := by
  intro next transition
  cases transition

end Algo2LeanGenerated

open Algo2LeanGenerated

def entry_UnionFind___init__ (input : Ref_UnionFind × Int) : Frame :=
  (Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__))

def UnionFind.__init__.ValidInput (h : Heap) (input : Ref_UnionFind × Int) : Prop := is_UnionFind h input.1
def UnionFind.__init__.initial (h : Heap) (input : Ref_UnionFind × Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__))
def UnionFind.__init__.Run (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.__init__.initial h input) (.done h' (Result.fn_UnionFind___init__ output))
def UnionFind.__init__.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int) (trace : Transcript) : Prop :=
  _root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.__init__.initial h input) trace final
def UnionFind.__init__.Call (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__)) h' (Result.fn_UnionFind___init__ output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.__init__.CallFrom (state : Configuration) (finalHeap : Heap) (output : Unit) : Prop :=
  match state with
  | .active heap (Frame.fn_UnionFind___init__ pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind___init__ pc locals) finalHeap (Result.fn_UnionFind___init__ output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.__init__.load (input : Heap × (Ref_UnionFind × Int)) : Heap × (Ref_UnionFind × Int) := input
def UnionFind.__init__.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
  _root_.Algo.«union_find».UnionFind.__init__.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.__init__.Returns (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Unit) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.__init__.Run loaded.1 loaded.2 finalHeap my_output

-- Output and clock increments from one completed execution.
def UnionFind.__init__.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Unit) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.__init__.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.__init__.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«union_find».UnionFind.__init__.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.__init__.Returns input output := by
  obtain ⟨heap, execution, _⟩ := run
  exact ⟨heap, execution⟩
theorem UnionFind.__init__.Returns.withCost {input output}
    (run : _root_.Algo.«union_find».UnionFind.__init__.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.__init__.ReturnsWithCost input output costs := by
  obtain ⟨heap, execution⟩ := run
  exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.__init__.load input).1 heap, heap, execution, rfl⟩

theorem UnionFind.__init__.Call.run {before input after output}
    (call : _root_.Algo.«union_find».UnionFind.__init__.Call before input after output) :
    _root_.Algo.«union_find».UnionFind.__init__.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_UnionFind_find (input : Ref_UnionFind × Int) : Frame :=
  (Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find))

def UnionFind.find.ValidInput (h : Heap) (input : Ref_UnionFind × Int) : Prop := is_UnionFind h input.1
def UnionFind.find.initial (h : Heap) (input : Ref_UnionFind × Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find))
def UnionFind.find.Run (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Int) : Prop :=
  _root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.find.initial h input) (.done h' (Result.fn_UnionFind_find output))
def UnionFind.find.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int) (trace : Transcript) : Prop :=
  _root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.find.initial h input) trace final
def UnionFind.find.Call (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Int) : Prop :=
  _root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find)) h' (Result.fn_UnionFind_find output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.find.CallFrom (state : Configuration) (finalHeap : Heap) (output : Int) : Prop :=
  match state with
  | .active heap (Frame.fn_UnionFind_find pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind_find pc locals) finalHeap (Result.fn_UnionFind_find output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.find.load (input : Heap × (Ref_UnionFind × Int)) : Heap × (Ref_UnionFind × Int) := input
def UnionFind.find.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
  _root_.Algo.«union_find».UnionFind.find.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.find.Returns (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Int) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.find.Run loaded.1 loaded.2 finalHeap my_output

-- Output and clock increments from one completed execution.
def UnionFind.find.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Int) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.find.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.find.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«union_find».UnionFind.find.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.find.Returns input output := by
  obtain ⟨heap, execution, _⟩ := run
  exact ⟨heap, execution⟩
theorem UnionFind.find.Returns.withCost {input output}
    (run : _root_.Algo.«union_find».UnionFind.find.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.find.ReturnsWithCost input output costs := by
  obtain ⟨heap, execution⟩ := run
  exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.find.load input).1 heap, heap, execution, rfl⟩

theorem UnionFind.find.Call.run {before input after output}
    (call : _root_.Algo.«union_find».UnionFind.find.Call before input after output) :
    _root_.Algo.«union_find».UnionFind.find.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_UnionFind_union (input : Ref_UnionFind × Int × Int) : Frame :=
  (Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union))

def UnionFind.union.ValidInput (h : Heap) (input : Ref_UnionFind × Int × Int) : Prop := is_UnionFind h input.1
def UnionFind.union.initial (h : Heap) (input : Ref_UnionFind × Int × Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union))
def UnionFind.union.Run (h : Heap) (input : Ref_UnionFind × Int × Int) (h' : Heap) (output : Bool) : Prop :=
  _root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.union.initial h input) (.done h' (Result.fn_UnionFind_union output))
def UnionFind.union.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int × Int) (trace : Transcript) : Prop :=
  _root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.union.initial h input) trace final
def UnionFind.union.Call (h : Heap) (input : Ref_UnionFind × Int × Int) (h' : Heap) (output : Bool) : Prop :=
  _root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union)) h' (Result.fn_UnionFind_union output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.union.CallFrom (state : Configuration) (finalHeap : Heap) (output : Bool) : Prop :=
  match state with
  | .active heap (Frame.fn_UnionFind_union pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind_union pc locals) finalHeap (Result.fn_UnionFind_union output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.union.load (input : Heap × (Ref_UnionFind × Int × Int)) : Heap × (Ref_UnionFind × Int × Int) := input
def UnionFind.union.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int × Int)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
  _root_.Algo.«union_find».UnionFind.union.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.union.Returns (my_input : Heap × (Ref_UnionFind × Int × Int)) (my_output : Bool) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.union.Run loaded.1 loaded.2 finalHeap my_output

-- Output and clock increments from one completed execution.
def UnionFind.union.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int × Int)) (my_output : Bool) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
  ∃ finalHeap, _root_.Algo.«union_find».UnionFind.union.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.union.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«union_find».UnionFind.union.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.union.Returns input output := by
  obtain ⟨heap, execution, _⟩ := run
  exact ⟨heap, execution⟩
theorem UnionFind.union.Returns.withCost {input output}
    (run : _root_.Algo.«union_find».UnionFind.union.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.union.ReturnsWithCost input output costs := by
  obtain ⟨heap, execution⟩ := run
  exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.union.load input).1 heap, heap, execution, rfl⟩

theorem UnionFind.union.Call.run {before input after output}
    (call : _root_.Algo.«union_find».UnionFind.union.Call before input after output) :
    _root_.Algo.«union_find».UnionFind.union.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_UnionFind (input : Int) : Frame :=
  (Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind))

def UnionFind.ValidInput (_h : Heap) (_input : Int) : Prop := True
def UnionFind.initial (h : Heap) (input : Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind))
def UnionFind.Run (h : Heap) (input : Int) (h' : Heap) (output : Ref_UnionFind) : Prop :=
  _root_.Algo.«union_find».UnionFind.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.initial h input) (.done h' (Result.fn_UnionFind output))
def UnionFind.ValidHeapTranscript (h : Heap) (input : Int) (trace : Transcript) : Prop :=
  _root_.Algo.«union_find».UnionFind.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.initial h input) trace final
def UnionFind.Call (h : Heap) (input : Int) (h' : Heap) (output : Ref_UnionFind) : Prop :=
  _root_.Algo.«union_find».UnionFind.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind)) h' (Result.fn_UnionFind output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_UnionFind) : Prop :=
  match state with
  | .active heap (Frame.fn_UnionFind pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind pc locals) finalHeap (Result.fn_UnionFind output)
  | _ => False
-- The value view gives each sequence input its own object.
def UnionFind.load (input : Int) : Heap × (Int) :=
  let h0 : Heap := {}
  (h0, input)
def UnionFind.ValidTranscript (my_input : Int) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.load my_input
  _root_.Algo.«union_find».UnionFind.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.Returns (my_input : Int) (my_output : Heap × (Ref_UnionFind)) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.load my_input
  _root_.Algo.«union_find».UnionFind.Run loaded.1 loaded.2 my_output.1 my_output.2

-- Output and clock increments from one completed execution.
def UnionFind.ReturnsWithCost (my_input : Int) (my_output : Heap × (Ref_UnionFind)) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«union_find».UnionFind.load my_input
  _root_.Algo.«union_find».UnionFind.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem UnionFind.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«union_find».UnionFind.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.Returns input output := by
  obtain ⟨execution, _⟩ := run
  exact execution
theorem UnionFind.Returns.withCost {input output}
    (run : _root_.Algo.«union_find».UnionFind.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.ReturnsWithCost input output costs := by
  exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.load input).1 output.1, run, rfl⟩

theorem UnionFind.Call.run {before input after output}
    (call : _root_.Algo.«union_find».UnionFind.Call before input after output) :
    _root_.Algo.«union_find».UnionFind.Run before input after output :=
  ⟨call.1, call.2.root⟩

end Algo.«union_find»
Source
https://github.com/lunjiah/algo2lean/blob/0f79d5e4242e6477531c9ee4410409f5b1c92f76/examples/kruskal/union_find.algo

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me