Asymptotically optimal, Coq-verified meldable heaps, AKA priority queues

Latest on Hackage:2.0.3

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow to host generated Haddocks.

BSD3 licensed by Jim Apple
Maintained by JimApple

A heap is a container supporting the insertion of elements and the extraction of the minimum element. This library additionally supports melding two heaps. This library models the implementation of asymptotically optimal purely functional heaps given by Brodal and Okasaki in their paper "Optimal Purely Functional Priority Queues". It has been proved correct using the Coq proof assistant. The proofs are included in the Cabal package.

A description of the differences between versions of this package is available at


Changes in version 2.0.3:

* Fixed export order in Strict to match that in Lazy and MeldableHeap.

Changes in version 2.0.2:

* Added link to CHANGELOG in cabal description

Changes in version 2.0.1:

* Added examples to Haddock documentation
* Added this CHANGELOG

Changes in version 2.0:

* Added a strict and a lazy version

Changes in version 1.1.2:

* Moved proof files from "extra-source-files" to "data-files" in cabal configuration

Changes in version 1.1.1:

* Change definition of meld to avoid use of Coq's "Function" feature, relying on higher-order fixpoints instead.
The Coq manual calls "Function" experimental.

Changes in version 1.1:

* Remove some unused parts of Coq files
* Change type parameter order of heap type to make it usable in contexts requiring kind * -> *
Depends on 1 package:
Used by 1 package:
comments powered byDisqus