« Up

quicksort-complexity 8.10.0 54 s

(2020-07-14 04:23:34 UTC)

Context

# Packages matching: installed
# Name              # Installed # Synopsis
base-bigarray       base
base-num            base        Num library distributed with the OCaml compiler
base-threads        base
base-unix           base
conf-findutils      1           Virtual package relying on findutils
conf-m4             1           Virtual package relying on m4
coq                 8.10.0      Formal proof management system
num                 0           The Num library for arbitrary-precision integer and rational arithmetic
ocaml               4.05.0      The OCaml compiler (virtual package)
ocaml-base-compiler 4.05.0      Official 4.05.0 release
ocaml-config        1           OCaml Switch Configuration
ocamlfind           1.8.1       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.10" & < "8.11~"}
]
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.10.0.tar.gz"
  checksum: "md5=c3b2ccbc5f13d56f46e99b51fef90a04"
}

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.10.0 coq.8.10.0
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 2h opam install -y --deps-only coq-quicksort-complexity.8.10.0 coq.8.10.0
Return code
0
Duration
4 s

Install

Command
opam list; echo; ulimit -Sv 16000000; timeout 2h opam install -y -v coq-quicksort-complexity.8.10.0 coq.8.10.0
Return code
0
Duration
54 s

Installation size

Total: 5 M

  • 323 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_utils.vo
  • 250 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_utils.glob
  • 201 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/vec.vo
  • 165 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.vo
  • 155 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/vec.glob
  • 146 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/arith_lems.vo
  • 126 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.glob
  • 125 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.vo
  • 121 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.vo
  • 103 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.vo
  • 93 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.vo
  • 88 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.vo
  • 87 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.glob
  • 85 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/indices.vo
  • 83 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.vo
  • 79 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/expec.vo
  • 78 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_worst.vo
  • 75 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_parts.vo
  • 73 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.vo
  • 72 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree.vo
  • 71 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cases.vo
  • 70 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.vo
  • 69 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/U.vo
  • 68 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/util.vo
  • 67 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.vo
  • 66 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.glob
  • 65 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.vo
  • 64 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.vo
  • 63 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.vo
  • 60 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cases.glob
  • 60 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monads.vo
  • 58 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.vo
  • 54 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_list.vo
  • 53 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/indices.glob
  • 50 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sort_order.vo
  • 48 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/arith_lems.glob
  • 47 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.vo
  • 45 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/harmonic.vo
  • 44 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_utils.v
  • 43 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.vo
  • 41 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_correct.vo
  • 40 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/NDP.vo
  • 39 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.glob
  • 39 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.vo
  • 38 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/U.glob
  • 37 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_below.vo
  • 36 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.glob
  • 35 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/expec.glob
  • 34 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.glob
  • 34 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/vec.v
  • 33 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.glob
  • 33 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.glob
  • 32 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.glob
  • 31 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/skip_list.vo
  • 30 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.glob
  • 29 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_parts.glob
  • 29 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sort_order.glob
  • 28 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/util.glob
  • 28 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monads.glob
  • 27 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree.glob
  • 27 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.glob
  • 23 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.glob
  • 23 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_worst.glob
  • 19 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.glob
  • 18 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.glob
  • 16 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.v
  • 15 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.glob
  • 15 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.glob
  • 15 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.v
  • 14 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_list.glob
  • 14 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.v
  • 12 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/indices.v
  • 11 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_below.glob
  • 11 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/arith_lems.v
  • 9 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cases.v
  • 9 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_correct.glob
  • 9 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/harmonic.glob
  • 8 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/skip_list.glob
  • 7 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/U.v
  • 7 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/expec.v
  • 7 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.v
  • 7 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sort_order.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monads.v
  • 5 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/util.v
  • 5 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_parts.v
  • 5 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.v
  • 5 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.v
  • 5 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.glob
  • 4 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_worst.v
  • 4 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.v
  • 4 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.v
  • 3 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_list.v
  • 3 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/NDP.glob
  • 3 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.v
  • 3 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.v
  • 3 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.v
  • 2 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_below.v
  • 2 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/skip_list.v
  • 2 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_correct.v
  • 2 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/harmonic.v
  • 2 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.v
  • 1 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/NDP.v

Uninstall

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

Sources are on GitHub. © Guillaume Claret.