AFTD Auto-Formalizing Theoretical Domains

bpe_lex_best_pair

def

Selects the adjacent pair with the largest number of nonoverlapping occurrences in the string, breaking ties by lexicographical order of integer IDs, or returns none if no pair occurs.

Statement

def bpe_lex_best_pair (s : List ℕ) : Option (ℕ × ℕ)
Defined in
OP-1536
Verified
11 Nov 2026
Axioms
none listed
Built on 2
  • bpe_pair_betterComparison between two symbol pairs in a string, preferring the pair with strictly more nonoverlapping occurrences, and breaking ties by…
  • bpe_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
Used by 1
  • bpe_lex_stepPerforms one greedy full BPE merge step replacing the chosen lexicographically earliest maximal pair with fresh symbol z, leaving the…

Read back from the Lean

A function bpe_lex_best_pair that takes a list of natural numbers s and returns an Option (ℕ × ℕ): 1. If the list of adjacent pairs s.zip s.tail is empty (that is, if s has length 0 or 1), it returns none. 2. Otherwise, let p :: ps = s.zip s.tail. It computes best by folding over ps starting from p, replacing the accumulator acc with a candidate pair q whenever bpe_pair_better s q acc is true. 3. If bpe_pair_count best.1 best.2 s = 0, it returns none; otherwise, it returns some best.

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

/-- The greedy pair with maximal nonoverlapping count, broken by lexicographic order. -/
def bpe_lex_best_pair (s : List ℕ) : Option (ℕ × ℕ) :=
  match s.zip s.tail with
  | [] => none
  | p :: ps =>
    let best := ps.foldl (fun acc q => if bpe_pair_better s q acc then q else acc) p
    if bpe_pair_count best.1 best.2 s = 0 then none
    else some best
See it in the graphDiscuss this resultChallenge it