« Up

quicksort-complexity 8.5.0 3 m 0 s 🏆

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
camlp4              4.04+1       Camlp4 is a system for writing extensible parsers for programming languages
conf-findutils      1            Virtual package relying on findutils
coq                 8.5.0~camlp4 Formal proof management system
num                 0            The Num library for arbitrary-precision integer and rational arithmetic
ocaml               4.04.2       The OCaml compiler (virtual package)
ocaml-base-compiler 4.04.2       Official 4.04.2 release
ocaml-config        1            OCaml Switch Configuration
ocamlbuild          0.14.2       OCamlbuild is a build system with builtin rules to easily build most OCaml projects
# opam file:
opam-version: "2.0"
maintainer: "matej.kosik@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.5" & < "8.6~"}
]
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.5.0.tar.gz"
  checksum: "md5=8234353fc0384b441e777523f7542440"
}

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.5.0 coq.8.5.0~camlp4
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.5.0 coq.8.5.0~camlp4
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.5.0 coq.8.5.0~camlp4
Return code
0
Duration
3 m 0 s

Installation size

Total: 5 M

  • 334 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_utils.vo
  • 247 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_utils.glob
  • 202 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/vec.vo
  • 171 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.vo
  • 153 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/vec.glob
  • 146 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/arith_lems.vo
  • 127 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.vo
  • 125 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.glob
  • 118 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.vo
  • 105 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.vo
  • 99 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.vo
  • 91 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.vo
  • 87 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.glob
  • 84 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/indices.vo
  • 82 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.vo
  • 78 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_worst.vo
  • 78 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/expec.vo
  • 72 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.vo
  • 71 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/util.vo
  • 70 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree.vo
  • 70 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cases.vo
  • 69 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.vo
  • 69 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_parts.vo
  • 68 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/U.vo
  • 66 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.vo
  • 63 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.vo
  • 63 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.vo
  • 62 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.vo
  • 62 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monads.vo
  • 62 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.glob
  • 58 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cases.glob
  • 56 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.vo
  • 53 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_list.vo
  • 53 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sort_order.vo
  • 53 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/indices.glob
  • 48 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/arith_lems.glob
  • 45 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.vo
  • 44 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_utils.v
  • 44 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/harmonic.vo
  • 41 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.vo
  • 41 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.vo
  • 39 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.glob
  • 39 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_below.vo
  • 39 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_correct.vo
  • 38 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/NDP.vo
  • 37 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/U.glob
  • 35 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.glob
  • 34 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/expec.glob
  • 34 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.glob
  • 34 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/vec.v
  • 33 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.glob
  • 33 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.glob
  • 32 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.glob
  • 31 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/skip_list.vo
  • 30 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.glob
  • 29 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sort_order.glob
  • 28 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/util.glob
  • 27 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_parts.glob
  • 27 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monads.glob
  • 26 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree.glob
  • 26 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.glob
  • 23 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.glob
  • 22 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_worst.glob
  • 19 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.glob
  • 17 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.glob
  • 16 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sums_and_averages.v
  • 15 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.glob
  • 15 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.glob
  • 15 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_avg_complexity.v
  • 14 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_list.glob
  • 14 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_definitions.v
  • 12 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/indices.v
  • 11 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/arith_lems.v
  • 11 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_below.glob
  • 9 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_correct.glob
  • 9 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cases.v
  • 9 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/harmonic.glob
  • 7 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/skip_list.glob
  • 7 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_nondet_avg_complexity.v
  • 7 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/U.v
  • 7 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/expec.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_sound_cmps.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_case_split.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/insertion_sort.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_tree_monad.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_expec.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monads.v
  • 6 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/sort_order.v
  • 5 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/util.v
  • 5 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_parts.v
  • 5 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/fix_measure_utils.v
  • 5 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_monad_trans.v
  • 5 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.glob
  • 4 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_worst.v
  • 4 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_CM_U_expec_cost_eq.v
  • 4 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_cmp_prob.v
  • 3 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/ne_list.v
  • 3 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/NDP.glob
  • 3 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_seqs.v
  • 3 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_det_parts.v
  • 3 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/list_length_expec.v
  • 2 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/nat_below.v
  • 2 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/skip_list.v
  • 2 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/qs_correct.v
  • 2 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/harmonic.v
  • 2 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/monoid_tree_monad.v
  • 1 K ../ocaml-base-compiler.4.04.2/lib/coq/user-contrib/QuicksortComplexity/NDP.v

Uninstall 🧹

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

Sources are on GitHub © Guillaume Claret 🐣