pqueue-mtl 1.0.1 → 1.0.2

raw patch · 2 files changed

+37/−26 lines, 2 filesdep ~stateful-mtl

Dependency ranges changed: stateful-mtl

Files

• Control/Monad/Queue/Heap.hs +35/−24
• pqueue-mtl.cabal +2/−2

@@ -1,37 +1,48 @@ {-# LANGUAGE RankNTypes, FlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses, UndecidableInstances #-} -module Control.Monad.Queue.Heap (HeapM, runHeapM) where+module Control.Monad.Queue.Heap (HeapM, HeapT, runHeapM, runHeapMIO, runHeapT) where -import Control.Monad.State.Strict-import Control.Monad.Array+import Control.Monad.ST import Control.Monad.ST.Class-import Control.Monad+import Control.Monad.Array.ArrayT+import Control.Monad.Array.Class++import Control.Monad.State.Strict import Control.Monad.RWS.Class import Control.Monad.Queue.Class-import Control.Monad.Identity +import Control.Monad+ -- | Monad based on an array implementation of a standard binary heap.-newtype HeapM s e a = HeapM {execHeapM :: StateT Int (ArrayM s e) a} +type HeapM s e = HeapT s e (ST s)+-- | Monad transformer based on an array implementation of a standard binary heap.+newtype HeapT s e m a = HeapT {execHeapT :: StateT Int (ArrayT s e m) a} deriving (Monad, MonadST s, MonadFix, MonadReader r, MonadWriter w) -instance Monad (HeapM s e) where-	return x = HeapM (return x)-	m >>= k = HeapM (execHeapM m >>= execHeapM . k)+instance MonadTrans (HeapT s e) where+	lift = HeapT . lift . lift -instance MonadST s (HeapM s e) where-	liftST = HeapM . liftST+instance (MonadST s m, MonadState t m) => MonadState t (HeapT s e m) where+	get = lift get+	put = lift . put  -- | Runs an 'HeapM' computation starting with an empty heap. runHeapM :: Ord e => (forall s . HeapM s e a) -> a-runHeapM m = runArrayM_ 16 (evalStateT (execHeapM m) 0)+runHeapM m = runST $ runHeapT m +runHeapMIO :: Ord e => HeapM RealWorld e a -> IO a+runHeapMIO m = stToIO $ runHeapT m++runHeapT :: (MonadST s m, Monad m) => HeapT s e m a -> m a+runHeapT m = runArrayT_ 16 (evalStateT (execHeapT m) 0)+ -- | Runs an 'HeapM' computation starting with a heap initialized to hold the specified list.  (Since this can be done with linear preprocessing, this is more efficient than inserting the elements one by one.)-runHeapTOn :: (Ord e) => (forall s . HeapM s e a) -- ^ The transformer operation.-				-> Int -- ^ The starting size of the heap (must be equal to the length of the list)-				-> [e] -- ^ The initial contents of the heap-				-> a-runHeapTOn m n l = runArrayM_ 16 $ flip evalStateT n $ do	mapM_ (uncurry unsafeWriteAt) (zip [0..] l)-								mapM_ (\ i -> unsafeReadAt i >>= heapDown n i) [0..n-1]-								execHeapM m+-- runHeapTOn :: (Ord e) => (forall s . HeapM s e a) -- ^ The transformer operation.+-- 				-> Int -- ^ The starting size of the heap (must be equal to the length of the list)+-- 				-> [e] -- ^ The initial contents of the heap+-- 				-> a+-- runHeapTOn m n l = runArrayM_ 16 $ flip evalStateT n $ do	mapM_ (uncurry unsafeWriteAt) (zip [0..] l)+-- 								mapM_ (\ i -> unsafeReadAt i >>= heapDown n i) [0..n-1]+-- 								execHeapM m  ensureHeap :: MonadArray e m => Int -> m () ensureHeap n = do	cap <- getSize@@ -55,17 +66,17 @@ 					if al < x then unsafeWriteAt i al >> unsafeWriteAt lch x else unsafeWriteAt i x 			GT	-> unsafeWriteAt i x -instance (Ord e) => MonadQueue e (HeapM s e) where-	queuePeek = HeapM $ do	+instance (MonadST s m, Monad m, Ord e) => MonadQueue e (HeapT s e m) where+	queuePeek = HeapT $ do	 		size <- get 		if size > 0 then liftM Just (unsafeReadAt 0) else return Nothing-	queueInsert x = HeapM $ do+	queueInsert x = HeapT $ do 		size <- get 		ensureHeap (size+1) 		put (size + 1) 		heapUp size x-	queueDelete = HeapM $ do+	queueDelete = HeapT $ do 		size <- get 		put (size - 1) 		unsafeReadAt (size - 1) >>= heapDown (size - 1) 0 >> unsafeWriteAt (size-1) undefined-	queueSize = HeapM get+	queueSize = HeapT get

@@ -1,6 +1,6 @@  name:		pqueue-mtl-version:	1.0.1+version:	1.0.2 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@@ -9,7 +9,7 @@ license-file:	LICENSE author:		Louis Wasserman maintainer:	wasserman.louis@gmail.com-build-Depends:	base, ghc-prim, mtl, containers, stateful-mtl >= 1.0.1 , MaybeT+build-Depends:	base, ghc-prim, mtl, containers, stateful-mtl >= 1.0.2 , 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 ghc-options: