AFTD Auto-Formalizing Theoretical Domains

greedy_pack_list

def

Given a remaining capacity remCap : ℝ and a list of timely items, greedy_pack_list remCap : List TimelyItem → Finset TimelyItem recursively scans the list, returning a Finset TimelyItem containing each item whose size does not exceed the remaining capacity (inserting it into the finset and subtracting its size from the remaining capacity), and skipping items that do not fit.

Statement

noncomputable def greedy_pack_list (remCap : ℝ) : List TimelyItem → Finset TimelyItem
Defined in
arXiv:2611.09611, Section 2
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…
  • instLinearOrderTimelyItemThe linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function…
Used by 1
  • thrifty_greedy_stepFor a non-empty set of remaining timely items R with witness hR : R.Nonempty, thrifty_greedy_step R hR returns the TimelyBin whose…

Read back from the Lean

greedy_pack_list is a function that takes a remaining capacity remCap : ℝ and a list of TimelyItems, returning a Finset TimelyItem defined recursively: - For the empty list [], it returns the empty finset ∅. - For a cons cell x :: xs, if x.size ≤ remCap, it inserts x into greedy_pack_list (remCap - x.size) xs; otherwise, it returns greedy_pack_list remCap xs.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Greedily packs a list of items into remaining capacity, returning a finset of packed items. -/
noncomputable def greedy_pack_list (remCap : ℝ) : List TimelyItem → Finset TimelyItem
| [] => ∅
| x :: xs =>
  open Classical in
  if x.size ≤ remCap then
    insert x (greedy_pack_list (remCap - x.size) xs)
  else
    greedy_pack_list remCap xs
See it in the graphDiscuss this resultChallenge it