« Up

quicksort-complexity 8.7.0 2 m 0 s 🏆

Context

# Packages matching: installed
# Name              # Installed # Synopsis
base-bigarray       base
base-num            base        Num library distributed with the OCaml compiler
base-ocamlbuild     base        OCamlbuild binary and libraries distributed with the OCaml compiler
base-threads        base
base-unix           base
camlp5              7.14        Preprocessor-pretty-printer of OCaml
conf-findutils      1           Virtual package relying on findutils
conf-perl           2           Virtual package relying on perl
coq                 8.7.1+1     Formal proof management system
num                 0           The Num library for arbitrary-precision integer and rational arithmetic
ocaml               4.02.3      The OCaml compiler (virtual package)
ocaml-base-compiler 4.02.3      Official 4.02.3 release
ocaml-config        1           OCaml Switch Configuration
ocamlfind           1.9.6       A library manager for OCaml
# opam file:
opam-version: "2.0"
maintainer: "Hugo.Herbelin@inria.fr"
homepage: "https://github.com/coq-contribs/quicksort-complexity"
license: "BSD"
build: [make "-j%{jobs}%"]
install: [make "install"]
remove: ["rm" "-R" "%{lib}%/coq/user-contrib/QuicksortComplexity"]
depends: [
  "ocaml"
  "coq" {>= "8.7" & < "8.8~"}
]
tags: [ "keyword: quicksort" "keyword: complexity" "keyword: average-case" "category: Computer Science/Decision Procedures and Certified Algorithms/Correctness proofs of algorithms" "date: 2010-06" ]
authors: [ "Eelis" ]
bug-reports: "https://github.com/coq-contribs/quicksort-complexity/issues"
dev-repo: "git+https://github.com/coq-contribs/quicksort-complexity.git"
synopsis: "Proofs of Quicksort's worst- and average-case complexity"
description: """
The development contains:
- a set of monads and monad transformers for measuring a (possibly nondeterministic) algorithm's use of designated operations;
- monadically expressed deterministic and nondeterministic implementations of Quicksort;
- proofs of these implementations' worst- and average case complexity.
Most of the development is documented in the TYPES 2008 paper "A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq", available at the homepage."""
flags: light-uninstall
url {
  src:
    "https://github.com/coq-contribs/quicksort-complexity/archive/v8.7.0.tar.gz"
  checksum: "md5=489ce4001974d6aae7171cbace5a4ba9"
}

Lint

Command
true
Return code
0

Dry install 🏜️

Dry install with the current Coq version:

Command
opam install -y --show-action coq-quicksort-complexity.8.7.0 coq.8.7.1+1
Return code
0

Dry install without Coq/switch base, to test if the problem was incompatibility with the current Coq/OCaml version:

Command
true
Return code
0

Install dependencies

Command
opam list; echo; ulimit -Sv 4000000; timeout 4h opam install -y --deps-only coq-quicksort-complexity.8.7.0 coq.8.7.1+1
Return code
0
Duration
1 m 0 s

Install 🚀

Command
opam list; echo; ulimit -Sv 16000000; timeout 4h opam install -y -v coq-quicksort-complexity.8.7.0 coq.8.7.1+1
Return code
0
Duration
2 m 0 s

Installation size

Total: 5 M

  • 333 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_utils.vo
  • 247 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_utils.glob
  • 204 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/vec.vo
  • 170 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.vo
  • 154 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/vec.glob
  • 147 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/arith_lems.vo
  • 128 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.vo
  • 125 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.glob
  • 119 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.vo
  • 109 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.vo
  • 101 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.vo
  • 92 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.vo
  • 87 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.glob
  • 84 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/indices.vo
  • 82 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.vo
  • 79 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/expec.vo
  • 79 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_worst.vo
  • 74 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_parts.vo
  • 73 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.vo
  • 71 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/util.vo
  • 71 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cases.vo
  • 71 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree.vo
  • 70 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.vo
  • 69 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/U.vo
  • 67 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.vo
  • 67 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.vo
  • 65 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.vo
  • 64 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.vo
  • 63 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monads.vo
  • 62 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.glob
  • 58 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cases.glob
  • 57 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.vo
  • 54 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_list.vo
  • 53 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sort_order.vo
  • 53 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/indices.glob
  • 48 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/harmonic.vo
  • 48 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/arith_lems.glob
  • 46 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.vo
  • 44 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_utils.v
  • 42 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.vo
  • 41 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.vo
  • 40 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_correct.vo
  • 39 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_below.vo
  • 39 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.glob
  • 39 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/NDP.vo
  • 37 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/U.glob
  • 35 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.glob
  • 34 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/expec.glob
  • 34 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/vec.v
  • 34 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.glob
  • 33 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.glob
  • 33 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.glob
  • 31 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.glob
  • 31 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/skip_list.vo
  • 30 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.glob
  • 29 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sort_order.glob
  • 28 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/util.glob
  • 27 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_parts.glob
  • 27 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monads.glob
  • 27 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree.glob
  • 26 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.glob
  • 23 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.glob
  • 22 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_worst.glob
  • 19 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.glob
  • 17 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.glob
  • 16 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.v
  • 15 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.glob
  • 15 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.glob
  • 15 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.v
  • 14 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_list.glob
  • 14 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.v
  • 12 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/indices.v
  • 11 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/arith_lems.v
  • 11 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_below.glob
  • 9 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_correct.glob
  • 9 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cases.v
  • 9 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/harmonic.glob
  • 7 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/skip_list.glob
  • 7 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.v
  • 7 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/U.v
  • 7 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/expec.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monads.v
  • 6 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/sort_order.v
  • 5 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/util.v
  • 5 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_parts.v
  • 5 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.v
  • 5 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.v
  • 5 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.glob
  • 4 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_worst.v
  • 4 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.v
  • 4 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.v
  • 3 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/ne_list.v
  • 3 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/NDP.glob
  • 3 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.v
  • 3 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.v
  • 3 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.v
  • 2 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/nat_below.v
  • 2 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/skip_list.v
  • 2 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/qs_correct.v
  • 2 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/harmonic.v
  • 2 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.v
  • 1 K ../ocaml-base-compiler.4.02.3/lib/coq/user-contrib/QuicksortComplexity/NDP.v

Uninstall 🧹

Command
opam remove -y coq-quicksort-complexity.8.7.0
Return code
0
Missing removes
none
Wrong removes
none

Sources are on GitHub © Guillaume Claret 🐣