pqueue-mtl 1.0.4 → 1.0.5

raw patch · 6 files changed

+59/−9 lines, 6 files

Files

• Control/Monad/Queue/Heap.hs +3/−1
• Data/Queue/PQueue.hs +5/−3
• Data/Queue/QueueHelpers.hs +2/−2
• Data/Queue/ReverseQueue.hs +0/−1
• Data/Queue/SkewQueue.hs +47/−0
• pqueue-mtl.cabal +2/−2

@@ -1,5 +1,7 @@ {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleInstances, GeneralizedNewtypeDeriving, TypeFamilies, UndecidableInstances #-} +{- | Safe implementation of an array-backed binary heap.  The 'HeapT' transformer requires that the underlying monad provide a 'MonadST' instance, meaning that the bottom-level monad must be 'ST'.  This critical restriction protects referential transparency, disallowing multi-threaded behavior as if the '[]' monad were at the bottom level. (The 'HeapM' monad takes care of the 'ST' bottom level automatically.)+-} module Control.Monad.Queue.Heap (HeapM, HeapT, runHeapM, runHeapMOn, runHeapT, runHeapTOn) where  import Control.Monad.Array.ArrayT@@ -43,7 +45,7 @@  				-> [e] -- ^ The initial contents of the heap  				-> m a runHeapTOn m n l = runArrayT_ n $ flip evalStateT n $ do	mapM_ (uncurry unsafeWriteAt) (zip [0..n-1] l)-								mapM_ (\ i -> unsafeReadAt i >>= heapDown n i) [0..n-1]+								mapM_ (\ i -> unsafeReadAt i >>= heapDown n i) [n-1,n-2..0] 								execHeapT m  instance (MonadST m, Monad m, Ord e) => MonadQueue (HeapT e m) where

@@ -15,12 +15,11 @@  import Control.Monad +-- Like with SkewQueue, the real meat of the pairing heap is very succinctly presented: it's all in the Monoid instance, and in the extract method, where the fusing method from QueueHelpers (already used for QueueHelpers' generic merging implementation) provides all the magic.  Everything else is deliciously succinct boilerplate, largely derived from HeapQ's Monoid instance.+ data Tree e = T e [Tree e] newtype PQueue e = PQ (HeapQ (Tree e)) deriving (Monoid, Queuelike) -single :: e -> HeapQ (Tree e)-single x = HQ 1 $ Just (T x [])- instance Ord e => Monoid (Tree e) where 	-- no actual mzero instance, but induces a correct Monoid instance for Heap e 	t1@(T x1 ts1) `mappend` t2@(T x2 ts2) @@ -47,6 +46,9 @@ 	extract (HQ n t) = fmap (\ (T x ts) ->  (x, HQ (n-1) (fusing ts))) t 	toList_ = maybe [] flatten . heap 	size = elts++single :: e -> HeapQ (Tree e)+single x = HQ 1 $ Just (T x [])  flatten :: Tree e -> [e] flatten (T x ts) = [x] ++ concatMap flatten ts

@@ -4,8 +4,8 @@ {------------------  This module builds structure common to instances of functional heaps, using monoidal structure.-Functional heaps consist of a size tag and a monoidally structured tree type, probably lacking a true mzero.-This module brings monoidal stucture from the tree type to the HeapQ, and provides a common mconcat implementation+A HeapQ consists of a size tag and a monoidally structured tree type, probably lacking a 'true' mzero.+This module automatically lifts monoidal stucture from the tree type to the HeapQ, and provides a common mconcat implementation that provides balanced, linear-time heap merging.  Then a new heap can work as follows:  data FooHeap e = ...

@@ -4,7 +4,6 @@ module Data.Queue.ReverseQueue (Down(..), ReverseQueue) where  import Data.Queue.Class-import Data.Monoid  newtype Down a = Down {unDown :: a} deriving (Eq) 

@@ -0,0 +1,47 @@+{-# LANGUAGE FlexibleInstances, GeneralizedNewtypeDeriving, TypeFamilies #-}+{-# OPTIONS -fno-warn-missing-methods -fno-warn-name-shadowing #-}++{- | A standard, compact implementation of a skew queue, which offers merging, insertion, and deletion in amortized logarithmic time and size and peek-min in constant time.  +-}+module Data.Queue.SkewQueue (SkewQueue) where++import Data.Queue.Class+import Data.Queue.QueueHelpers++import GHC.Exts++import Data.Monoid+import Data.Ord++-- Confession: This is as much a toy implementation as anything else, due to the sheer sexy compactness with which skew queues can be implemented in Haskell, especially with the automatically provided monoid structure from QueueHelpers.  The meat of the skew queue implementation is entirely contained in the Monoid instance; everything else is deliciously brief boilerplate.++data BTree e = Tr {treeMin :: e, _left, _right :: Maybe (BTree e)}+newtype SkewQueue e = SQ (HeapQ (BTree e)) deriving (Monoid, Queuelike)++instance Ord e => Monoid (BTree e) where+	mappend = let t1 `meld` t2 = case order (comparing treeMin) t1 t2 of+			(Tr x l r, t') -> Tr x (endoMaybe meld r (Just t')) l +		in meld+++instance Ord e => Queuelike (HeapQ (BTree e)) where+	{-# INLINE mergeAll #-}+	type QueueKey (HeapQ (BTree e)) = e++	empty = mempty+	singleton = single+	fromList xs = mconcat (map single xs)++	merge = mappend+	mergeAll = mconcat+	+	extract (HQ n t) = fmap (\ (Tr x l r) -> (x, HQ n (l `mappend` r))) t+	size = elts+	toList_ = flatten . heap++single :: e -> HeapQ (BTree e)+single x =  HQ 1 $ Just (Tr x Nothing Nothing)++flatten :: Maybe (BTree e) -> [e]+flatten h = build (flattenFB h) where+	flattenFB h c n = maybe n (\ (Tr x l r) -> x `c` flattenFB l c (flattenFB r c n)) h

@@ -1,6 +1,6 @@  name:		pqueue-mtl-version:	1.0.4+version:	1.0.5 synopsis:	Fully encapsulated monad transformers with queuelike functionality. description:	Contains several implementations of data structures implementing a /single-in, single-out/ paradigm, and implements monad transformers for their safe use.  The monad transformer part of the library includes tools to fully encapsulate single-threaded use of a priority queue in a monad, including an array-based heap implementation. tested-with:	GHC@@ -11,6 +11,6 @@ maintainer:	wasserman.louis@gmail.com build-Depends:	base, ghc-prim, mtl, containers, stateful-mtl == 1.0.4 , MaybeT build-type:	Simple-Exposed-modules:Control.Monad.Queue, Control.Monad.Queue.Instances, Control.Monad.Queue.Class, Control.Monad.Queue.Heap, Control.Monad.Queue.QueueT, Data.Queue, Data.Queue.PQueue, Data.Queue.FibQueue, Data.Queue.Class, Data.Queue.Instances, Data.Queue.Stack, Data.Queue.Queue, Data.Queue.ReverseQueue+Exposed-modules:Control.Monad.Queue, Control.Monad.Queue.Instances, Control.Monad.Queue.Class, Control.Monad.Queue.Heap, Control.Monad.Queue.QueueT, Data.Queue, Data.Queue.PQueue, Data.Queue.FibQueue, Data.Queue.Class, Data.Queue.Instances, Data.Queue.Stack, Data.Queue.Queue, Data.Queue.ReverseQueue, Data.Queue.SkewQueue other-modules: Data.Queue.QueueHelpers ghc-options: