CostM
structureimported Lean
Writer monad over an arbitrary additive monoid C. A CostM C A is a return value of type A together with an accumulated cost in C. The cost field aggregates via + and 0 of C. See the file docstring for the design rationale and for the choices of C that recover specific complexity measures.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in @[ext] structure CostM (C : Type*) (A : Type*)
- Defined in
- EconCSLib, `CostM`
- 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← CostM (EconCSLib/Foundation/CostM.lean:136): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 36
- 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.bindSequential composition. The cost of
m >>= fism.cost + (f m.ret).cost. - CostM.instLawfulMonad
CostM Cis a lawful monad wheneverCis an additive monoid. - CostM.cost_seqLeftCostM.cost_seqLeft
- CostM.cost_bindCostM.cost_bind
- CostM.ret_bindCostM.ret_bind
- CostM.cost_mapCostM.cost_map
- CostM.tickCharge a cost of
c, returning unit. Use inside ado-block. - CostM.ret_mapCostM.ret_map
- CostM.instBindCostM.instBind
- CostM.instSeqRightCostM.instSeqRight
- CostM.parListN-ary parallel composition over a
Listof independentCostMoperands. Returns are paired into a list in the original order; the cost… - CostM.ret_parCostM.ret_par
- CostM.pureLift a pure value at zero cost.
- CostM.BoundedThe cost of
alg iis bounded bybound (size i)for every inputi. - CostM.instFunctorCostM.instFunctor
- CostM.ret_pureCostM.ret_pure
- CostM.ret_parListCostM.ret_parList
- CostM.ret_seqCostM.ret_seq
- CostM.instSeqCostM.instSeq
- CostM.ret_seqLeftCostM.ret_seqLeft
- CostM.ret_seqRightCostM.ret_seqRight
- CostM.IsPolyBoundedSpecialization of
BoundedforC = ℕ: cost is polynomial in input size. - CostM.cost_pureCostM.cost_pure
- CostM.cost_seqRightCostM.cost_seqRight
- CostM.ret_tickCostM.ret_tick
- CostM.cost_parList_consCostM.cost_parList_cons
- CostM.cost_seqCostM.cost_seq
- CostM.parList_nilCostM.parList_nil
- CostM.instPureCostM.instPure
- CostM.cost_parCostM.cost_par
- CostM.instMonadCostM.instMonad
- CostM.instSeqLeftCostM.instSeqLeft
- CostM.parIndependent (parallel) composition of two
CostMcomputations. The return is the pair of return values; the cost is the sup of the two… - CostM.cost_parListCostM.cost_parList
- CostM.cost_tickCostM.cost_tick
- CostM.instCoeHeadCoerce a
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- Writer monad over an arbitrary additive monoid `C`. A `CostM C A` is a return value of type `A` together with an accumulated cost in `C`. The `cost` field aggregates via `+` and `0` of `C`. See the file docstring for the design rationale and for the choices of `C` that recover specific complexity measures. -/ @[ext] structure CostM (C : Type*) (A : Type*) where /-- The result of the computation. -/ ret : A /-- The accumulated cost in `C`. -/ cost : C