« Up

quicksort-complexity 8.8.0 59 s

(2019-10-10 18:58:50 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
camlp5              7.10        Preprocessor-pretty-printer of OCaml
conf-m4             1           Virtual package relying on m4
coq                 8.8.2       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.8" & < "8.9~"}
]
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.8.0.tar.gz"
  checksum: "md5=86b001d6780b06f5e725cb197ea61d8e"
}

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.8.0 coq.8.8.2
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 60m opam install -y --deps-only coq-quicksort-complexity.8.8.0 coq.8.8.2
Return code
0
Duration
3 s

Install

Command
opam list; echo; ulimit -Sv 4000000; timeout 1h opam install -y -v coq-quicksort-complexity.8.8.0 coq.8.8.2
Return code
0
Duration
59 s

Installation size

Total: 5 M

  • 330 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_utils.vo
  • 248 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/list_utils.glob
  • 204 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/vec.vo
  • 162 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.vo
  • 154 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/vec.glob
  • 144 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/arith_lems.vo
  • 129 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.vo
  • 125 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.glob
  • 120 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.vo
  • 110 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
  • 91 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
  • 84 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.vo
  • 80 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/expec.vo
  • 79 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_worst.vo
  • 74 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_parts.vo
  • 74 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.vo
  • 73 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cases.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_CM_U_expec_cost_eq.vo
  • 70 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/insertion_sort.vo
  • 68 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.vo
  • 66 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/util.vo
  • 66 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.vo
  • 66 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.vo
  • 65 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.glob
  • 64 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/monads.vo
  • 59 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cases.glob
  • 58 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.vo
  • 55 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/ne_list.vo
  • 54 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sort_order.vo
  • 53 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/indices.glob
  • 49 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/harmonic.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
  • 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
  • 42 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.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/nat_below.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
  • 37 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/U.glob
  • 35 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.glob
  • 34 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/sort_order.glob
  • 28 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_parts.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
  • 26 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/arith_lems.v
  • 11 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/nat_below.glob
  • 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/qs_cases.v
  • 9 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/harmonic.glob
  • 7 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/qs_nondet_avg_complexity.v
  • 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
  • 6 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/ne_tree.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/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/monads.v
  • 6 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/sort_order.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_CM_U_expec_cost_eq.v
  • 4 K ../ocaml-base-compiler.4.05.0/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.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.8.0
Return code
0
Missing removes
none
Wrong removes
none