From: rsiddharth <s@ricketyspace.net>
To: 27367@debbugs.gnu.org
Cc: rsiddharth <s@ricketyspace.net>
Subject: [bug#27367] [PATCH 05/15] gnu: Add ghc-psqueues.
Date: Thu, 15 Jun 2017 01:23:50 +0000 [thread overview]
Message-ID: <20170615012400.8414-5-s@ricketyspace.net> (raw)
In-Reply-To: <20170615012400.8414-1-s@ricketyspace.net>
* gnu/packages/haskell.scm (ghc-psqueues): New variable.
---
gnu/packages/haskell.scm | 65 ++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 65 insertions(+)
diff --git a/gnu/packages/haskell.scm b/gnu/packages/haskell.scm
index 9ab889f36..a766bd051 100644
--- a/gnu/packages/haskell.scm
+++ b/gnu/packages/haskell.scm
@@ -8418,4 +8418,69 @@ are the bottleneck of web servers.")
bytestrings and their hexademical representation.")
(license license:bsd-3)))
+(define-public ghc-psqueues
+ (package
+ (name "ghc-psqueues")
+ (version "0.2.2.3")
+ (source
+ (origin
+ (method url-fetch)
+ (uri (string-append "https://hackage.haskell.org/package/"
+ "psqueues-" version "/"
+ "psqueues-" version ".tar.gz"))
+ (sha256
+ (base32
+ "1dd6xv1wjxj1xinx155b14hijw8fafrg4096srzdzj7xyqq7qxbd"))))
+ (build-system haskell-build-system)
+ (inputs
+ `(("ghc-hashable" ,ghc-hashable)))
+ (native-inputs
+ `(("ghc-hunit" ,ghc-hunit)
+ ("ghc-quickcheck" ,ghc-quickcheck)
+ ("ghc-tagged" ,ghc-tagged)
+ ("ghc-test-framework" ,ghc-test-framework)
+ ("ghc-test-framework-hunit" ,ghc-test-framework-hunit)
+ ("ghc-test-framework-quickcheck2" ,ghc-test-framework-quickcheck2)))
+ (home-page "https://github.com/bttr/psqueues")
+ (synopsis "Pure priority search queues")
+ (description "The psqueues package provides
+@uref{http://en.wikipedia.org/wiki/Priority_queue, Priority Search Queues} in
+three different flavors:
+
+@itemize
+@item @code{OrdPSQ k p v}, which uses the @code{Ord k} instance to provide
+fast insertion, deletion and lookup. This implementation is based on Ralf
+Hinze's @uref{http://citeseer.ist.psu.edu/hinze01simple.html, A Simple
+Implementation Technique for Priority Search Queues}.
+
+Hence, it is similar to the @uref{http://hackage.haskell.org/package/PSQueue,
+PSQueue} library, although it is considerably faster and provides a slightly
+different API.
+
+@item @code{IntPSQ p v} is a far more efficient implementation. It fixes the
+key type to @code{Int} and uses a
+@code{http://en.wikipedia.org/wiki/Radix_tree, radix tree}
+(like @code{IntMap}) with an additional min-heap property.
+
+@item @code{HashPSQ k p v} is a fairly straightforward extension
+of @code{IntPSQ}: it simply uses the keys' hashes as indices in the
+@code{IntPSQ}. If there are any hash collisions, it uses an
+@code{OrdPSQ} to resolve those. The performance of this implementation
+is comparable to that of @code{IntPSQ}, but it is more widely
+applicable since the keys are not restricted to @code{Int},
+but rather to any @code{Hashable} datatype.
+@end itemize
+
+Each of the three implementations provides the same API, so they can
+be used interchangeably.
+
+Typical applications of Priority Search Queues include:
+
+@itemize
+@item Caches, and more specifically LRU Caches;
+@item Schedulers;
+@item Pathfinding algorithms, such as Dijkstra's and A*.
+@end itemize")
+ (license license:bsd-3)))
+
;;; haskell.scm ends here
--
2.11.0
next prev parent reply other threads:[~2017-06-15 1:26 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <handler.27367.B.149747697323437.ack@debbugs.gnu.org>
2017-06-15 1:23 ` [bug#27367] [PATCH 01/15] gnu: Add ghc-wai-conduit rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 02/15] gnu: Add ghc-http-date rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 03/15] gnu: Add ghc-simple-sendfile rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 04/15] gnu: Add ghc-hex rsiddharth
2017-06-15 1:23 ` rsiddharth [this message]
2017-06-15 1:23 ` [bug#27367] [PATCH 06/15] gnu: Add ghc-glob rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 07/15] gnu: Add ghc-http2 rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 08/15] gnu: ghc-auto-update: Update to 0.1.4 rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 09/15] gnu: ghc-wai: Update to 3.2.1.1 rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 10/15] gnu: ghc-wai-extra: Update to 3.0.13.1 rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 11/15] gnu: Add ghc-warp rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 12/15] gnu: Add ghc-warp-tls rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 13/15] gnu: ghc-http-client: Update to 0.5.6.1 rsiddharth
2017-06-15 1:23 ` [bug#27367] [PATCH 14/15] gnu: ghc-http-client-tls: Update to 0.3.4.1 rsiddharth
2017-06-15 1:24 ` [bug#27367] [PATCH 15/15] gnu: Add ghc-http-conduit rsiddharth
2017-06-16 8:26 ` [bug#27367] [PATCH 01/15] gnu: Add ghc-wai-conduit Ludovic Courtès
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://guix.gnu.org/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170615012400.8414-5-s@ricketyspace.net \
--to=s@ricketyspace.net \
--cc=27367@debbugs.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/guix.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).