queues: Queue data structures.

[ bsd3, data, library ] [ Propose Tags ] [ Report a vulnerability ]

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.


[Skip to Readme]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0.0
Change log CHANGELOG.md
Dependencies base (>=4.15 && <4.21) [details]
Tested with ghc ==9.6.5, ghc ==9.8.2, ghc ==9.10.1
License BSD-3-Clause
Copyright Copyright (C) 2023-2024 Mitchell Dalvi Rosen, Travis Staton
Author Mitchell Dalvi Rosen, Travis Staton
Maintainer Mitchell Dalvi Rosen <mitchellwrosen@gmail.com>, Travis Staton <hello@travisstaton.com>
Revised Revision 3 made by mitchellwrosen at 2024-07-10T15:22:23Z
Category Data
Home page https://github.com/awkward-squad/queues
Bug tracker https://github.com/awkward-squad/queues/issues
Source repo head: git clone https://github.com/awkward-squad/queues.git
Uploaded by mitchellwrosen at 2024-03-03T21:04:05Z
Distributions NixOS:1.0.0, Stackage:1.0.0
Downloads 79 total (6 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-03-03 [all 1 reports]

Readme for queues-1.0.0

[back to package description]

queues

GitHub CI Hackage Stackage LTS Stackage Nightly Dependencies