queue is:package
Not on Stackage, so not searched.
Abstraction typeclasses for queue-like things.
Not on Stackage, so not searched.
A library of queuelike data structures, both functional and stateful.
Queue data structures.
Queue data structures, as described in
- Okasaki, Chris. "Simple and efficient purely functional queues and
deques." Journal of functional programming 5.4 (1995):
583-592.
- Okasaki, Chris. Purely Functional Data Structures. Diss.
Princeton University, 1996.
A queue has a "back" where new elements are enqueued, and a "front"
where elements are dequeued in the order that they were enqueued (last
in, first out).
The queues provided in this library also support an "enqueue at front"
operation, because the underlying representations happen to support
it, so you might technically refer to these data structures as
output-restricted deques.
In this library, it is helpful to think of the "front" being on the
left, because (though the direction is arbitrary) we are
consistent throughout, where it matters:
- List conversion functions associate the head of a list with the
front of a queue.
- The append operator xs <> ys creates a queue with
xs in front of ys.
- The Show instances draw the front of the queue on the
left.
Under "ephemeral" (or "single-threaded", or "linear") usage, wherein
one does not need to refer to an old version of a data structure after
mutating it:
- EphemeralQueue is 2.5x faster than and
allocates 0.50x as much memory as Queue.
- Queue is 2.6x faster than and allocates 0.40x
as much memory as Seq (from containers).
(These numbers vary from benchmark to benchmark and machine to
machine. Always perform your own experiments!)
While it is certainly common to use a queue ephemerally, it is unusual
for a Haskell data structure to require ephemeral usage to achieve its
stated bounds. A refactoring or change in requirements might cause
surprising changes in performance. That is why
EphemeralQueue
has a longer name and module name. When in doubt, use
Queue.
Pure priority search queues
The psqueues package provides
Priority Search Queues in three
different flavors.
- OrdPSQ k p v, which uses the Ord k instance to
provide fast insertion, deletion and lookup. This implementation is
based on Ralf Hinze's A Simple Implementation Technique for
Priority Search Queues. Hence, it is similar to the PSQueue
library, although it is considerably faster and provides a slightly
different API.
- IntPSQ p v is a far more efficient implementation. It
fixes the key type to Int and uses a radix tree (like
IntMap) with an additional min-heap property.
- HashPSQ k p v is a fairly straightforward extension of
IntPSQ: it simply uses the keys' hashes as indices in the
IntPSQ. If there are any hash collisions, it uses an
OrdPSQ to resolve those. The performance of this
implementation is comparable to that of IntPSQ, but it is
more widely applicable since the keys are not restricted to
Int, but rather to any Hashable datatype.
Each of the three implementations provides the same API, so they can
be used interchangeably. The benchmarks show how they perform relative
to one another, and also compared to the other Priority Search Queue
implementations on Hackage:
PSQueue and
fingertree-psqueue.
Typical applications of Priority Search Queues include:
- Caches, and more specifically LRU Caches;
- Schedulers;
- Pathfinding algorithms, such as Dijkstra's and A*.
Reliable, persistent, fast priority queues.
A fast, reliable priority queue implementation based on a binomial
heap.
Priority Search Queue
A
priority search queue efficiently supports the operations of
both a search tree and a priority queue. A
Binding is a product
of a key and a priority. Bindings can be inserted, deleted, modified
and queried in logarithmic time, and the binding with the least
priority can be retrieved in constant time. A queue can be built from
a list of bindings, sorted by keys, in linear time.
Not on Stackage, so not searched.
A typeclass and an implementation for double-ended queues.
Not on Stackage, so not searched.
A networked event handling framework for hooking into other programs.
Not on Stackage, so not searched.
A flexible job queue with exchangeable backends
Michael and Scott lock-free queues.
Michael and Scott queues are described in their PODC 1996 paper:
http://dl.acm.org/citation.cfm?id=248052.248106
These are single-ended concurrent queues based on a singlly linked
list and using atomic CAS instructions to swap the tail pointers. As a
well-known efficient algorithm they became the basis for Java's
ConcurrentLinkedQueue.
A strict, immutable, thread-safe, single-ended, bounded queue.
A strict, immutable, thread-safe, single-ended, bounded queue which
automatically forgets old values instead of blocking.
Not on Stackage, so not searched.
A job queue library
Fast concurrent queues much inspired by unagi-chan
"kazura-queue" provides an implementation of FIFO queue. It is faster
than Chan, TQueue or TChan by the benefit of fetch-and-add
instruction.
Main motivation of this package is to solve some difficulty of
"unagi-chan" package.
- In "unagi-chan", the item in the queue/chan can be lost when async
exception is throwed to the read thread while waiting for read.
(Although it has handler to recover lost item, it is difficult to keep
FIFO in such case)
- In "unagi-chan", garbage items of the queue cannot be collected
immediately. Since the buffer in the queue has the reference to the
items until the buffer is garbage-collected.
"kazura-queue" is slightly slower than "unagi-chan" instead of solving
these issues.
"kazura-queue" lost broadcast function to improve the second issue. It
means that kazura-queue is not "Chan" but is just "Queue".
Not on Stackage, so not searched.
A binding to the kqueue event library.
Not on Stackage, so not searched.
Haskell API for NATS messaging system
Not on Stackage, so not searched.
A PostgreSQL backed queue
Not on Stackage, so not searched.
A distributed worker backend for powerqueu
Not on Stackage, so not searched.
A high performance in memory and LevelDB backend for powerqueue
Not on Stackage, so not searched.
Simple implementation of a priority queue.
Not on Stackage, so not searched.
An implementation of a real-time concurrent queue
Not on Stackage, so not searched.
Stompl Client Library
Not on Stackage, so not searched.
Queues with verified and unverified versions.
Not on Stackage, so not searched.
Background jobs library for Yesod.
Not on Stackage, so not searched.
A Queue with a random (weighted) pick function