-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Fully encapsulated monad transformers with queuelike functionality.
--   
--   Contains several implementations of data structures implementing a
--   <i>single-in, single-out</i> 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. In general, the purely functional queue types can be
--   ordered in increasing order of speed on generic insertion/deletion
--   operations as follows: <a>Stack</a>, <a>Queue</a>, <a>PQueue</a>,
--   <a>IntQueue</a>, <a>SkewQueue</a>, <a>FQueue</a>, <a>Heap</a>.
--   (<a>PQueue</a>, <a>IntQueue</a>, and <a>SkewQueue</a> are all very
--   nearly the same speed.) Work is in progress on a van Emde Boas or
--   y-fast priority queue implementation, which provides sublogarithmic
--   functionality for all operations.
@package pqueue-mtl
@version 1.0.6


-- | Abstracts the implementation details of a single-insertion,
--   single-extraction queuelike structure.
module Data.Queue.Class

-- | Type that only orders on the key, ignoring the value completely;
--   frequently useful in priority queues, so made available here.
data (:->) e f
(:->) :: e -> f -> (:->) e f

-- | A generic type class encapsulating a generic queuelike structure, that
--   supports single-insertion and single-extraction; this abstraction
--   includes priority queues, stacks, and FIFO queues. There are many
--   minimal implementations, so each method lists the prerequisites for
--   its default implementation. Most implementations will implement
--   <a>empty</a>, (<a>singleton</a> and <a>merge</a>) or <a>insert</a>,
--   (<a>peek</a> and <a>delete</a>) or <a>extract</a>, and <a>size</a>.
class Queuelike q where { type family QueueKey q; { mergeAll = foldr merge empty q1 merge q2 = insertAll (toList q2) q1 toList_ = toList toList = unfoldr extract isEmpty = isNothing . peek size = length . toList_ fromList xs = insertAll xs empty singleton x = insert x empty empty = fromList [] delete = liftM snd . extract peek = liftM fst . extract extract = liftM2 (liftM2 (,)) peek delete insertAll = flip (foldr insert) insert = merge . singleton } }
insert :: (Queuelike q) => QueueKey q -> q -> q
insertAll :: (Queuelike q) => [QueueKey q] -> q -> q
extract :: (Queuelike q) => q -> Maybe (QueueKey q, q)
peek :: (Queuelike q) => q -> Maybe (QueueKey q)
delete :: (Queuelike q) => q -> Maybe q
empty :: (Queuelike q) => q
singleton :: (Queuelike q) => QueueKey q -> q
fromList :: (Queuelike q) => [QueueKey q] -> q
size :: (Queuelike q) => q -> Int
isEmpty :: (Queuelike q) => q -> Bool
toList :: (Queuelike q) => q -> [QueueKey q]
toList_ :: (Queuelike q) => q -> [QueueKey q]
merge :: (Queuelike q) => q -> q -> q
mergeAll :: (Queuelike q) => [q] -> q
instance (Ord f) => Ord (e :-> f)
instance (Eq f) => Eq (e :-> f)


-- | A basic implementation of a stack implementing the Queue abstraction.
module Data.Queue.Stack
data Stack e
instance Monoid (Stack e)
instance Queuelike (Stack e)


-- | A basic first-in, first-out queue implementation implementing the
--   <a>Queuelike</a> abstraction.
module Data.Queue.Queue
data Queue e
instance Monoid (Queue e)
instance Queuelike (Queue e)


-- | Generic queue wrapper to transform a min-queue into a max-queue.
module Data.Queue.ReverseQueue
newtype Down a
Down :: a -> Down a
unDown :: Down a -> a

-- | Wrapper around a generic queue that reverses the ordering on its
--   elements.
data ReverseQueue q e
instance (Eq a) => Eq (Down a)
instance (QueueKey (q (Down e)) ~ Down e, Queuelike (q (Down e))) => Queuelike (ReverseQueue q e)
instance (Ord a) => Ord (Down a)


-- | 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
data SkewQueue e
instance (Ord e) => Monoid (SkewQueue e)
instance (Ord e) => Queuelike (SkewQueue e)
instance (Ord e) => Monoid (BTree e)


-- | A small collection of specialized <a>Int</a>-indexed priority queues
--   dealing with both untagged <a>Int</a>s and association pairs with
--   <a>Int</a> keys. The implementation is a simple bootstrap from IntMap.
--   (Note: Duplicate keys <i>will</i> be counted separately. No guarantees
--   are made on the order in which values associated with equal keys are
--   returned.)
module Data.Queue.IntQueue

-- | A <a>Queuelike</a> type with <tt>QueueKey IntQueue ~ Int</tt>.
data IntQueue

-- | A <a>Queuelike</a> type with <tt>QueueKey (IntAssocQueue e) ~ e :-&gt;
--   Int</tt>.
data IntAssocQueue e
instance Queuelike (IntAssocQueue e)
instance Queuelike IntQueue


-- | An alternate implementation of a priority queue based on a
--   <i>Fibonacci heap</i>.
--   
--   Fibonacci heaps, while not quite as internally functional as pairing
--   heaps, are generally less ad-hoc and may prove useful for some uses
--   (as well as serving as a useful testbed). A Fibonacci heap can be
--   thought of as a lazier binomial heap, designed to better take
--   advantage of the fact that in a lazy language a series of modification
--   operations will likely all be computed at once, preferably as late as
--   possible. The Fibonacci heap supports all <a>Queuelike</a> operations
--   with the same time complexity as PQueue.
module Data.Queue.FibQueue
data FQueue e
instance (Ord e) => Queuelike (FQueue e)
instance (Ord e) => Monoid (FQueue e)


-- | An efficient implementation of a priority queue.
--   
--   The implementation of <a>PQueue</a> is based on a <i>pairing heap</i>,
--   a simple and efficient implementation of a general-purpose priority
--   queue. <a>PQueue</a> supports <a>insert</a>, <a>merge</a>, and
--   <a>peek</a> in constant time, and <a>extract</a> and <a>delete</a> in
--   logarithmic time.
module Data.Queue.PQueue
data PQueue e
instance (Ord e) => Monoid (PQueue e)
instance (Ord e) => Queuelike (PQueue e)
instance (Ord e) => Monoid (Tree e)

module Data.Queue.Instances

module Data.Queue

module Control.Monad.Queue.Class

-- | Typeclass abstraction of a monad with access to a mutable queue.
--   Minimal implementation: <a>queueInsert</a> or <a>queueInsertAll</a>,
--   <a>queuePeek</a>, <a>queueExtract</a> or <a>queueDelete</a>,
--   <a>queueSize</a>.
class (Monad m) => MonadQueue m where { type family QKey m; { queueExtract = do mx <- queuePeek case mx of { Nothing -> return Nothing Just {} -> queueDelete >> return mx } queueDelete = queueExtract >> return () queueInsert x = queueInsertAll [x] queueInsertAll = mapM_ queueInsert queueEmpty = liftM (== 0) queueSize } }
queueInsert :: (MonadQueue m) => QKey m -> m ()
queueInsertAll :: (MonadQueue m) => [QKey m] -> m ()
queueExtract :: (MonadQueue m) => m (Maybe (QKey m))
queueDelete :: (MonadQueue m) => m ()
queuePeek :: (MonadQueue m) => m (Maybe (QKey m))
queueEmpty :: (MonadQueue m) => m Bool
queueSize :: (MonadQueue m) => m Int
instance (MonadQueue m) => MonadQueue (ArrayT f m)
instance (MonadQueue m) => MonadQueue (IntMapT f m)
instance (MonadQueue m) => MonadQueue (ListT m)
instance (MonadQueue m) => MonadQueue (MaybeT m)
instance (Monoid w, MonadQueue m) => MonadQueue (WriterT w m)
instance (Monoid w, MonadQueue m) => MonadQueue (WriterT w m)
instance (MonadQueue m) => MonadQueue (ReaderT r m)
instance (MonadQueue m) => MonadQueue (StateT s m)
instance (MonadQueue m) => MonadQueue (StateT s m)


-- | Safe implementation of an array-backed binary heap. The <a>HeapT</a>
--   transformer requires that the underlying monad provide a
--   <a>MonadST</a> instance, meaning that the bottom-level monad must be
--   <a>ST</a>. This critical restriction protects referential
--   transparency, disallowing multi-threaded behavior as if the '[]' monad
--   were at the bottom level. (The <a>HeapM</a> monad takes care of the
--   <a>ST</a> bottom level automatically.)
module Control.Monad.Queue.Heap

-- | Monad based on an array implementation of a standard binary heap.
type HeapM s e = HeapT e (ST s)

-- | Monad transformer based on an array implementation of a standard
--   binary heap.
data HeapT e m a

-- | Runs an <a>HeapM</a> computation starting with an empty heap.
runHeapM :: (Ord e) => (forall s. HeapM s e a) -> a
runHeapMOn :: (Ord e) => (forall s. HeapM s e a) -> Int -> [e] -> a
runHeapT :: (MonadST m, Monad m) => HeapT e m a -> m a

-- | Runs an <a>HeapM</a> 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 :: (MonadST m, Monad m, Ord e) => HeapT e m a -> Int -> [e] -> m a
data UHeapT e m a
runUHeapT :: (MonadST m, Monad m, UA e, Ord e) => UHeapT e m a -> m a
instance (Monad m) => Monad (UHeapT e m)
instance (MonadFix m) => MonadFix (UHeapT e m)
instance (MonadReader r m) => MonadReader r (UHeapT e m)
instance (MonadWriter w m) => MonadWriter w (UHeapT e m)
instance (Monad m) => Monad (HeapT e m)
instance (MonadPlus m) => MonadPlus (HeapT e m)
instance (MonadFix m) => MonadFix (HeapT e m)
instance (MonadReader r m) => MonadReader r (HeapT e m)
instance (MonadWriter w m) => MonadWriter w (HeapT e m)
instance (MonadST m, Monad m, UA e, Ord e) => MonadQueue (UHeapT e m)
instance (MonadST m, Monad m, Ord e) => MonadQueue (HeapT e m)
instance (MonadState s m) => MonadState s (HeapT e m)
instance MonadTrans (HeapT e)


-- | A monad transformer allowing a purely functional queue implementation
--   (specifically, implementing the <a>Queuelike</a> abstraction) to be
--   used in a monadic, single-threaded fashion.
module Control.Monad.Queue.QueueT

-- | A monad transformer granting the underlying monad <tt>m</tt> access to
--   single-threaded actions on a queue.
newtype QueueT q m a
QueueT :: StateT q m a -> QueueT q m a
runQT :: QueueT q m a -> StateT q m a

-- | A monad controlling single-threaded access to a queue.
newtype QueueM q a
QueueM :: State q a -> QueueM q a
runQM :: QueueM q a -> State q a
type PQueueT e = QueueT (PQueue e)
type PQueueM e = QueueM (PQueue e)
type FibQueueT e = QueueT (FQueue e)
type FibQueueM e = QueueM (FQueue e)
type SkewQueueT e = QueueT (SkewQueue e)
type SkewQueueM e = QueueM (SkewQueue e)
type IntQueueT = QueueT IntQueue
type IntQueueM = QueueM IntQueue

-- | Unwraps a queue transformer, initializing it with an empty queue.
runQueueT :: (Monad m, Queuelike q) => QueueT q m a -> m a

-- | Unwraps a queue transformer, initializing it with a queue with the
--   specified contents.
runQueueTOn :: (Monad m, Queuelike q) => QueueT q m a -> [QueueKey q] -> m a

-- | Executes a computation in a queue monad, starting with an empty queue.
runQueueM :: (Queuelike q) => QueueM q a -> a

-- | Executes a computation in a queue monad, starting with a queue with
--   the specified contents.
runQueueMOn :: (Queuelike q) => QueueM q a -> [QueueKey q] -> a
instance MonadFix (QueueM q)
instance Monad (QueueM q)
instance (MonadReader r m) => MonadReader r (QueueT q m)
instance (MonadWriter w m) => MonadWriter w (QueueT q m)
instance (MonadIO m) => MonadIO (QueueT q m)
instance (MonadFix m) => MonadFix (QueueT q m)
instance (Monad m) => Monad (QueueT q m)
instance MonadTrans (QueueT q)
instance (Queuelike q) => MonadQueue (QueueM q)
instance (Monad m, Queuelike q) => MonadQueue (QueueT q m)
instance (MonadState s m) => MonadState s (QueueT q m)

module Control.Monad.Queue.Instances

module Control.Monad.Queue