type-indexed-queues

This library provides implementations of five different queues (binomial, pairing, skew, leftist, and Braun), each in two flavours: one verified, and one not. At the moment, only structural invariants are maintained. More information, and a walkthough of a couple implementations, can be found at this blog post. Comparisons of verified and unverified queues Both versions of each queue are provided for comparison: for instance, compare the standard leftist queue (in Data.Queue.Leftist): To its size-indexed counterpart (in Data.Queue.Indexed.Leftist): The invariant here (that the size of the left queue must always be less than that of the right) is encoded in the proof m <= n. With that in mind, compare the unverified and verified implementatons of merge: Verified: Using type families and typechecker plugins to encode the invariant The similarity is accomplished through overloading, and some handy functions. For instance, the second if-then-else works on boolean singletons, and the <=. function provides a proof of order along with its answer. The actual arithmetic is carried out at runtime on normal integers, rather than Peano numerals. These tricks are explained in more detail TypeLevel.Singletons and TypeLevel.Bool. A typechecker plugin does most of the heavy lifting, although there are some (small) manual proofs. Uses of verified queues The main interesting use of these sturctures is total traversable sorting (sort-traversable). An implementation of this is provided in Data.Traversable.Parts. I'm interested in finding out other uses for these kinds of structures.