Cslib.Algorithms.Lean.TimeM.instLawfulMonad
instanceimported Lean
TimeM is lawful so long as addition in the cost is associative and absorbs zero.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in instance Cslib.Algorithms.Lean.TimeM.instLawfulMonad [AddMonoid T'] : LawfulMonad (TimeM T')
- Defined in
- CSLib, `Cslib.Algorithms.Lean.TimeM.instLawfulMonad`
- Lean proof
- By Sorrachai Yingchareonthawornhcai, Eric Wieser, 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.Cslib.Algorithms.Lean.TimeM.instLawfulMonad← @Cslib/Algorithms/Lean/TimeM.lean:119 (Cslib/Algorithms/Lean/TimeM.lean:118): adapted
What was changed in
Cslib.Algorithms.Lean.TimeM.instLawfulMonad--- Cslib/Algorithms/Lean/TimeM.lean:118 () +++ as compiled here @@ -1,3 +1,4 @@ -/-- `TimeM` is lawful so long as addition in the cost is associative and absorbs zero. -/ -instance [AddMonoid T] : LawfulMonad (TimeM T) := .mk' +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +instance Cslib.Algorithms.Lean.TimeM.instLawfulMonad [AddMonoid T'] : LawfulMonad (TimeM T') := .mk' (id_map := fun x => rfl)
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 20
- Cslib.Algorithms.Lean.TimeMA monad for tracking time complexity of computations.
TimeM T αrepresents a computation that returns a value of typeαand… - Cslib.Algorithms.Lean.TimeM.instMonadOfAddZeroCslib.Algorithms.Lean.TimeM.instMonadOfAddZero
- Cslib.Algorithms.Lean.TimeM.ret_pureCslib.Algorithms.Lean.TimeM.ret_pure
- Cslib.Algorithms.Lean.TimeM.ret_bindCslib.Algorithms.Lean.TimeM.ret_bind
- Cslib.Algorithms.Lean.TimeM.ret_mapCslib.Algorithms.Lean.TimeM.ret_map
- Cslib.Algorithms.Lean.TimeM.ret_seqRightCslib.Algorithms.Lean.TimeM.ret_seqRight
- Cslib.Algorithms.Lean.TimeM.ret_seqLeftCslib.Algorithms.Lean.TimeM.ret_seqLeft
- Cslib.Algorithms.Lean.TimeM.ret_seqCslib.Algorithms.Lean.TimeM.ret_seq
- Cslib.Algorithms.Lean.TimeM.time_bindCslib.Algorithms.Lean.TimeM.time_bind
- Cslib.Algorithms.Lean.TimeM.time_pureCslib.Algorithms.Lean.TimeM.time_pure
- Cslib.Algorithms.Lean.TimeM.time_mapCslib.Algorithms.Lean.TimeM.time_map
- Cslib.Algorithms.Lean.TimeM.time_seqRightCslib.Algorithms.Lean.TimeM.time_seqRight
- Cslib.Algorithms.Lean.TimeM.time_seqLeftCslib.Algorithms.Lean.TimeM.time_seqLeft
- Cslib.Algorithms.Lean.TimeM.time_seqCslib.Algorithms.Lean.TimeM.time_seq
- Cslib.Algorithms.Lean.TimeM.instPureOfZeroCslib.Algorithms.Lean.TimeM.instPureOfZero
- Cslib.Algorithms.Lean.TimeM.instBindOfAddCslib.Algorithms.Lean.TimeM.instBindOfAdd
- Cslib.Algorithms.Lean.TimeM.instFunctorCslib.Algorithms.Lean.TimeM.instFunctor
- Cslib.Algorithms.Lean.TimeM.instSeqOfAddCslib.Algorithms.Lean.TimeM.instSeqOfAdd
- Cslib.Algorithms.Lean.TimeM.instSeqLeftOfAddCslib.Algorithms.Lean.TimeM.instSeqLeftOfAdd
- Cslib.Algorithms.Lean.TimeM.instSeqRightOfAddCslib.Algorithms.Lean.TimeM.instSeqRightOfAdd
- Cslib.Algorithms.Lean.TimeMA monad for tracking time complexity of computations.
- Used by 18
- Cslib.Algorithms.Lean.TimeM.mergeSort_timeTime complexity of mergeSort
- Cslib.Algorithms.Lean.TimeM.merge_permCslib.Algorithms.Lean.TimeM.merge_perm
- Cslib.Algorithms.Lean.TimeM.mergeMerges two lists into a single list, counting comparisons as time cost. Returns a
TimeM ℕ (List α)where the time represents the number… - Cslib.Algorithms.Lean.TimeM.mergeSort_time_leCslib.Algorithms.Lean.TimeM.mergeSort_time_le
- Cslib.Algorithms.Lean.TimeM.mergeSort_permCslib.Algorithms.Lean.TimeM.mergeSort_perm
- Cslib.Algorithms.Lean.TimeM.tickCreates a
TimeMcomputation with a time cost. - Cslib.Algorithms.Lean.TimeM.mergeSort_sortedCslib.Algorithms.Lean.TimeM.mergeSort_sorted
- Cslib.Algorithms.Lean.TimeM.merge_timeCslib.Algorithms.Lean.TimeM.merge_time
- Cslib.Algorithms.Lean.TimeM.ret_tickCslib.Algorithms.Lean.TimeM.ret_tick
- Cslib.Algorithms.Lean.TimeM.mergeSort_correctMergeSort is functionally correct.
- Cslib.Algorithms.Lean.TimeM.mergeSort_same_lengthCslib.Algorithms.Lean.TimeM.mergeSort_same_length
- Cslib.Algorithms.Lean.TimeM.sorted_mergeCslib.Algorithms.Lean.TimeM.sorted_merge
- Cslib.Algorithms.Lean.TimeM.mergeSortSorts a list using the merge sort algorithm, counting comparisons as time cost. Returns a
TimeM ℕ (List α)where the time represents the… - Cslib.Algorithms.Lean.TimeM.time_tickCslib.Algorithms.Lean.TimeM.time_tick
- Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_leSolve the recurrence
- Cslib.Algorithms.Lean.TimeM.merge_ret_length_eq_sumCslib.Algorithms.Lean.TimeM.merge_ret_length_eq_sum
- Cslib.Algorithms.Lean.TimeM.mem_either_mergeCslib.Algorithms.Lean.TimeM.mem_either_merge
- Cslib.Algorithms.Lean.TimeM.ret_mergeOur merge computes the one already in mathlib.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- `TimeM` is lawful so long as addition in the cost is associative and absorbs zero. -/ instance Cslib.Algorithms.Lean.TimeM.instLawfulMonad [AddMonoid T'] : LawfulMonad (TimeM T') := .mk' (id_map := fun x => rfl) (pure_bind := fun _ _ => by ext <;> simp) (bind_assoc := fun _ _ _ => by ext <;> simp [add_assoc]) (seqLeft_eq := fun _ _ => by ext <;> simp) (bind_pure_comp := fun _ _ => by ext <;> simp)