AFTD Auto-Formalizing Theoretical Domains

Cslib.Algorithms.Lean.TimeM.merge

defimported Lean

Merges two lists into a single list, counting comparisons as time cost. Returns a TimeM ℕ (List α) where the time represents the number of comparisons performed.

Statement

set_option relaxedAutoImplicit true in
open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM in
set_option autoImplicit false in
variable {α : Type} [LinearOrder α] in
def Cslib.Algorithms.Lean.TimeM.merge :  List α → List α → TimeM ℕ (List α)
Defined in
CSLib, `Cslib.Algorithms.Lean.TimeM.merge`
Lean proof
By Sorrachai Yingchareonthawornhcai, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Sorrachai Yingchareonthawornhcai. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 24
Used by 9

Lean source view module on GitHub

set_option quotPrecheck false
open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM
local macro "✓[" c:term "]" body:doElem : doElem => `(doElem| do TimeM.tick $c; $body:doElem)
local macro "✓" body:doElem : doElem => `(doElem| ✓[1] $body)
local notation:max "⟪" tm "⟫" => (TimeM.ret tm)

set_option relaxedAutoImplicit true in
open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM in
set_option autoImplicit false in
variable {α : Type} [LinearOrder α] in
/-- Merges two lists into a single list, counting comparisons as time cost. Returns a `TimeM ℕ (List α)` where the time represents the number of comparisons performed. -/
def Cslib.Algorithms.Lean.TimeM.merge :  List α → List α → TimeM ℕ (List α)
  | [], ys => return ys
  | xs, [] => return xs
  | x::xs', y::ys' => do
    ✓ let c := (x ≤ y : Bool)
    if c then
      let rest ← merge xs' (y::ys')
      return (x :: rest)
    else
      let rest ← merge (x::xs') ys'
      return (y :: rest)
See it in the graphDiscuss this resultChallenge it