« Up

quicksort-complexity 8.9.0 3 m 0 s 🏆

Context

# Packages matching: installed
# Name              # Installed # Synopsis
base-bigarray       base
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.9.1       Formal proof management system
num                 1.4         The legacy Num library for arbitrary-precision integer and rational arithmetic
ocaml               4.06.1      The OCaml compiler (virtual package)
ocaml-base-compiler 4.06.1      Official 4.06.1 release
ocaml-config        1           OCaml Switch Configuration
ocamlfind           1.9.5       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.9" & < "8.10~"}
]
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.9.0-1.tar.gz"
  checksum: "md5=9fa8d740e916e98f6f46d8dc7c2e7f30"
}

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.9.0 coq.8.9.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.9.0 coq.8.9.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.9.0 coq.8.9.1
Return code
0
Duration
3 m 0 s

Installation size

Total: 5 M

  • 326 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_utils.vo
  • 249 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_utils.glob
  • 201 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/vec.vo
  • 158 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.vo
  • 154 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/vec.glob
  • 141 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/arith_lems.vo
  • 126 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.glob
  • 124 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.vo
  • 118 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.vo
  • 104 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.vo
  • 91 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.vo
  • 87 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.vo
  • 87 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.glob
  • 83 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/indices.vo
  • 82 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.vo
  • 79 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/expec.vo
  • 77 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_worst.vo
  • 73 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_parts.vo
  • 72 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.vo
  • 71 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cases.vo
  • 70 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree.vo
  • 69 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.vo
  • 68 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/U.vo
  • 66 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.vo
  • 66 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/util.vo
  • 65 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.glob
  • 64 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.vo
  • 63 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.vo
  • 63 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.vo
  • 60 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monads.vo
  • 59 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cases.glob
  • 56 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.vo
  • 53 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_list.vo
  • 53 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/indices.glob
  • 50 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sort_order.vo
  • 48 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/arith_lems.glob
  • 46 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.vo
  • 45 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/harmonic.vo
  • 44 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_utils.v
  • 42 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.vo
  • 40 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_correct.vo
  • 39 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.vo
  • 39 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.glob
  • 39 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/NDP.vo
  • 38 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_below.vo
  • 37 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/U.glob
  • 35 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.glob
  • 34 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/expec.glob
  • 34 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.glob
  • 34 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/vec.v
  • 33 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.glob
  • 33 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.glob
  • 32 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.glob
  • 30 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.glob
  • 30 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/skip_list.vo
  • 29 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sort_order.glob
  • 28 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_parts.glob
  • 28 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/util.glob
  • 28 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monads.glob
  • 27 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree.glob
  • 26 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.glob
  • 23 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.glob
  • 23 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_worst.glob
  • 19 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.glob
  • 18 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.glob
  • 16 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.v
  • 15 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.glob
  • 15 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.glob
  • 15 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.v
  • 14 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_list.glob
  • 14 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.v
  • 12 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/indices.v
  • 11 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/arith_lems.v
  • 11 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_below.glob
  • 9 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_correct.glob
  • 9 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cases.v
  • 9 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/harmonic.glob
  • 7 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/skip_list.glob
  • 7 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.v
  • 7 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/U.v
  • 7 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/expec.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/sort_order.v
  • 6 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monads.v
  • 5 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/util.v
  • 5 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_parts.v
  • 5 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.v
  • 5 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.v
  • 5 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.glob
  • 4 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_worst.v
  • 4 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.v
  • 4 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.v
  • 3 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/ne_list.v
  • 3 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/NDP.glob
  • 3 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.v
  • 3 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.v
  • 3 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.v
  • 2 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/nat_below.v
  • 2 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/skip_list.v
  • 2 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/qs_correct.v
  • 2 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/harmonic.v
  • 2 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.v
  • 1 K ../ocaml-base-compiler.4.06.1/lib/coq/user-contrib/QuicksortComplexity/NDP.v

Uninstall 🧹

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

Sources are on GitHub © Guillaume Claret 🐣