AFTD Auto-Formalizing Theoretical Domains

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
Used by 1

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 []
| _, _ => []
See it in the graphDiscuss this resultChallenge it