logo
首页技术栈工具库讨论
type-indexed-queues
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.
mailbox-count
mailbox-count
Usage: Mailbox-count produces a simple count of mailboxes that exist per-domain in some SQL database. The default queries are compatible with the schema used by PostfixAdmin http://postfixadmin.sourceforge.net/, but it is possible to supply your own queries via the --summary-query and --detail-query options. The summary report lists each domain, along with the number of mailboxes owned by that domain. The order is determined by the summary query, which lists the domains alphabetically by default. The default detail report shows the same, but also contains a list of each individual mailbox (again in alphabetical order) belonging to the domains. Input: None. Output: Either a summary, or detailed report (with --detail) of the number of mailboxes per-domain contained in the database. Options: The name of the database (or file, if SQLite) to which we should connect. Default: The name of the current user (Postgres only). Produce a detailed report listing all mailboxes by domain. SQL query used to produce the detail report. This should return the set of all (domain, username) pairs. See the default value for an example. Default: "SELECT domain,username FROM mailbox ORDER BY domain;" Hostname where the database is located (Postgres-only). Default: None, a UNIX domain socket connection is attempted (Postgres only) Password used to connect to the database (Postgres-only). Default: None (assumes passwordless authentication) --port Port number used to connect to the database (Postgres-only). Default: None, a UNIX domain socket connection is attempted (Postgres only) SQL query used to produce the summary report. This should return (domain, user count) pairs. See the default value for an example. Default: "SELECT domain,COUNT(username) FROM mailbox GROUP BY domain ORDER BY domain;" Username used to connect to the database (Postgres-only). Default: The current user Examples: The default summary report: The more detailed report: