[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

05/15: gnu: Add ghc-psqueues.

From: Ludovic Courtès
Subject: 05/15: gnu: Add ghc-psqueues.
Date: Fri, 16 Jun 2017 04:33:57 -0400 (EDT)

civodul pushed a commit to branch master
in repository guix.

commit aba85f8c385e6c4c67bd786fcc253413ff186c1f
Author: rsiddharth <address@hidden>
Date:   Thu Jun 15 01:23:50 2017 +0000

    gnu: Add ghc-psqueues.
    * gnu/packages/haskell.scm (ghc-psqueues): New variable.
    Signed-off-by: Ludovic Courtès <address@hidden>
 gnu/packages/haskell.scm | 65 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)

diff --git a/gnu/packages/haskell.scm b/gnu/packages/haskell.scm
index 73160e4..26a3d9a 100644
--- a/gnu/packages/haskell.scm
+++ b/gnu/packages/haskell.scm
@@ -8395,4 +8395,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 "")
+    (source
+     (origin
+       (method url-fetch)
+       (uri (string-append "";
+                           "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 "";)
+    (synopsis "Pure priority search queues")
+    (description "The psqueues package provides
address@hidden://, Priority Search Queues} 
+three different flavors:
address@hidden @code{OrdPSQ k p v}, which uses the @code{Ord k} instance to 
+fast insertion, deletion and lookup.  This implementation is based on Ralf
+Hinze's @uref{, A Simple
+Implementation Technique for Priority Search Queues}.
+Hence, it is similar to the @uref{,
+PSQueue} library, although it is considerably faster and provides a slightly
+different API.
address@hidden @code{IntPSQ p v} is a far more efficient implementation.  It 
fixes the
+key type to @code{Int} and uses a
address@hidden://, radix tree}
+(like @code{IntMap}) with an additional min-heap property.
address@hidden @code{HashPSQ k p v} is a fairly straightforward extension
+of @code{IntPSQ}: it simply uses the keys' hashes as indices in the
address@hidden  If there are any hash collisions, it uses an
address@hidden 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.
address@hidden itemize
+Each of the three implementations provides the same API, so they can
+be used interchangeably.
+Typical applications of Priority Search Queues include:
address@hidden Caches, and more specifically LRU Caches;
address@hidden Schedulers;
address@hidden Pathfinding algorithms, such as Dijkstra's and A*.
address@hidden itemize")
+    (license license:bsd-3)))
 ;;; haskell.scm ends here

reply via email to

[Prev in Thread] Current Thread [Next in Thread]