longest_common_prefix
def
The longest common prefix of two lists is their maximal shared initial segment.
Statement
def longest_common_prefix {α : Type*} [DecidableEq α] : List α → List α → List α
- Defined in
- arXiv:2611.13676 Lemma 3.1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 1
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- Used by 1
- longest_common_prefix_nil_leftThe longest common prefix of the empty list and any list is empty.
Read back from the Lean
For a type α with decidable equality ([DecidableEq α]), longest_common_prefix is a function taking two lists l₁ and l₂ of elements of α and returning a list of elements of α, defined recursively by pattern matching:
- If both lists are non-empty, with forms x :: xs and y :: ys: if x = y, it returns x :: longest_common_prefix xs ys; if x ≠ y, it returns [].
- If either list is empty, it returns [].
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 longest common prefix of two lists. -/ def longest_common_prefix {α : Type*} [DecidableEq α] : List α → List α → List α | x :: xs, y :: ys => if x = y then x :: longest_common_prefix xs ys else [] | _, _ => []