CostM.Bounded
defimported Lean
The cost of alg i is bounded by bound (size i) for every input i.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u in variable {C : Type*} {A B : Type u} in def CostM.Bounded {Input Output : Type*} [LE C] (alg : Input → CostM C Output) (size : Input → ℕ) (bound : ℕ → C) : Prop
- Defined in
- EconCSLib, `CostM.Bounded`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(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.30.0.CostM.Bounded← CostM.Bounded (EconCSLib/Foundation/CostM.lean:316): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 30
- CostM.instCoeHeadCoerce a
CostM C Ato its return value, dropping the cost. Use this in contexts where the expected type isA; pair with.costfor… - CostM.instLawfulMonad
CostM Cis a lawful monad wheneverCis an additive monoid. - CostM.ret_parCostM.ret_par
- CostM.ret_parListCostM.ret_parList
- CostM.ret_tickCostM.ret_tick
- CostM.cost_parList_consCostM.cost_parList_cons
- CostM.parList_nilCostM.parList_nil
- CostM.cost_parCostM.cost_par
- CostM.cost_parListCostM.cost_parList
- CostM.cost_tickCostM.cost_tick
- CostMWriter monad over an arbitrary additive monoid
C. ACostM C Ais a return value of typeAtogether with an accumulated cost inC.… - CostM.ret_pureCostM.ret_pure
- CostM.ret_bindCostM.ret_bind
- CostM.ret_mapCostM.ret_map
- CostM.ret_seqLeftCostM.ret_seqLeft
- CostM.ret_seqRightCostM.ret_seqRight
- CostM.ret_seqCostM.ret_seq
- CostM.cost_pureCostM.cost_pure
- CostM.cost_bindCostM.cost_bind
- CostM.cost_mapCostM.cost_map
- CostM.cost_seqLeftCostM.cost_seqLeft
- CostM.cost_seqRightCostM.cost_seqRight
- CostM.cost_seqCostM.cost_seq
- CostM.instPureCostM.instPure
- CostM.instBindCostM.instBind
- CostM.instFunctorCostM.instFunctor
- CostM.instSeqCostM.instSeq
- CostM.instSeqLeftCostM.instSeqLeft
- CostM.instSeqRightCostM.instSeqRight
- CostM.instMonadCostM.instMonad
- CostM.instCoeHeadCoerce a
- Used by 1
- CostM.IsPolyBoundedSpecialization of
BoundedforC = ℕ: cost is polynomial in input size.
- CostM.IsPolyBoundedSpecialization of
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u in variable {C : Type*} {A B : Type u} in /-- The cost of `alg i` is bounded by `bound (size i)` for every input `i`. -/ def CostM.Bounded {Input Output : Type*} [LE C] (alg : Input → CostM C Output) (size : Input → ℕ) (bound : ℕ → C) : Prop := ∀ i, (alg i).cost ≤ bound (size i)