Let's say I want to prove a bound on the number of a certain operation used by a function (such as proving a bound on the number of comparisons used by a sorting algorithm). What techniques/libraries should I be considering for doing that?
Bounds about a specific algorithm are one kind of problem; bounds about a class of algorithms are a different problem. https://coq.discourse.group/t/trying-to-prove-sort-algorithm-correctness-for-specific-n-in-search-for-hints/1076/11?u=blaisorblade is relevant to the second.
@Malcolm Sharpe Have a look at this thread [1].
[1] https://sympa.inria.fr/sympa/arc/coq-club/2022-07/msg00008.html
Thanks for the links. My conclusions:
(This made me curious what's the most accessible library for monads in Coq, and that seems to be coq-ext-lib, which is in coq-platform.)
Malcolm Sharpe has marked this topic as resolved.
I’d like to offer that I’m working on a new sub-library for my category-theory library that aims to make Monads very easy to work with in Coq, while leveraging the power of the larger library when proving that some construction is, in fact, a lawful Monad.
Last updated: Oct 05 2023 at 02:01 UTC