fifo_fetch
def
Updating a FIFO queue of size k ≥ 1 upon fetching a new page v: the oldest page (front of the queue) is evicted and v is appended to the back.
Statement
def fifo_fetch {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : FifoQueue α k
- Defined in
- arXiv:2610.18767 Section 3.1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- FifoQueueA first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
- Used by 1
- rank_potential_online_payment_boundFor any type α with decidable equality, any k ≥ 1, any FIFO queue q of capacity k, any offline cache cOpt of cardinality k, and any page v…
Read back from the Lean
Given a type α with decidable equality, an implicit natural number k, a proof that 1 ≤ k, a FIFO queue q : FifoQueue α k, an element v : α, and a proof that v ∉ q.pages, fifo_fetch defines a new FifoQueue α k whose pages list is obtained by removing the first element (head) of q.pages and appending v to the end (tail ++ [v]).
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
/-- FIFO queue update upon fetching a page: evict head, append to tail. -/ def fifo_fetch {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : FifoQueue α k := have hlen : q.pages.length = k := q.length_eq have h_ne : q.pages ≠ [] := by intro h; rw [h] at hlen; simp at hlen; omega match h_cons : q.pages with | [] => False.elim (h_ne h_cons) | head :: tail => { pages := tail ++ [v] length_eq := by have h1 : (head :: tail).length = k := by rw [← h_cons, hlen] simp only [List.length_cons] at h1 simp only [List.length_append, List.length_singleton] omega nodup := by have hnd : (head :: tail).Nodup := by rw [← h_cons]; exact q.nodup rw [List.nodup_cons] at hnd rw [List.nodup_append] refine ⟨hnd.2, List.nodup_singleton v, ?_⟩ intro x hx y hy simp only [List.mem_singleton] at hy subst hy intro heq; subst heq have : x ∈ q.pages := by rw [h_cons]; exact List.mem_cons_of_mem head hx exact hv this }