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


-- | Lazy-Spined Monadic Priority Queues
--   
--   This library provides a priority queue data structure that is meant to
--   be used primarily as a control structure, in the vein of list and
--   Logic. The PriorityQueue data structure in question is an instance of
--   Applicative, Alternative, and Monad classes much like the standard
--   list data type. In addition, it also tracks the cost incurred by each
--   computation it stores, and provides operations for pruning overly
--   expansive branches.
@package lazy-priority-queue
@version 0.1.0.2

module Data.PriorityQueue

-- | A lazy-spined priority queue where the type parameters t c a are:
--   
--   <ul>
--   <li>t for a phantom that can be either Pruned for a single-item
--   container or Branching for a growing priority queue;</li>
--   <li>c for the cost type, like Sum Int; and</li>
--   <li>a for the values</li>
--   </ul>
data PQueue t c a
data Branching
data Pruned

-- | Relax the <a>Pruned</a> phantom constraint, allowing the queue to
--   become <a>Branching</a>.
branchable :: PQueue Pruned c a -> PQueue t c a

-- | Prune away all stored values except the one with the least penalty,
--   making the queue <a>Pruned</a>.
prune :: PQueue t c a -> PQueue Pruned c a

-- | Prune away all stored values more expensive than the given cost.
pruneAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a

-- | Prune away all stored values more expensive than the given cost and a
--   less expensive alternative value.
pruneAlternativesAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a

-- | Maps each item contained in the queue, supplying the item's cost as
--   first argument
mapWithCost :: Monoid c => (c -> a -> b) -> PQueue t c a -> PQueue t c b

-- | Filter away from the queue the values that the argument function maps
--   to <a>False</a>
filter :: (a -> Bool) -> PQueue t c a -> PQueue t c a

-- | Fold together all stored values that share the same priority.
foldPeers :: (a -> a -> a) -> PQueue t c a -> PQueue t c a

-- | Minimize the queue structure. This operation forces the entire spine
--   of the queue and its every level.
canonical :: Semigroup c => PQueue t c a -> PQueue t c a

-- | Assuming the stored values belong to a cancellative monoid, prune away
--   all extraneous values and factors using the supplied function that
--   calculates the sum and difference of the two values, if there is any
--   difference, and the monoid null. &gt; fold (pruneSubsets plusDiff
--   mempty pq) == fold pq &gt; where plusDiff u a &gt; | gcd u a == a =
--   Nothing &gt; | d <a>a - gcd u a = Just (u &lt;</a> d, d)
pruneSubsets :: (a -> b -> Maybe (a, b)) -> a -> PQueue t c b -> PQueue t c b

-- | Subtract the first argument cost GCD from the cost of every value in
--   the second argument
strip :: (Ord c, Num c) => PQueue Pruned c a -> PQueue t c b -> PQueue t c b

-- | Returns the pair of the GCD of all the penalties and the penalties
--   without the GCD &gt; gcd <a>*</a> rest == f &gt; where (gcd, rest) =
--   stripCommon f
stripCommon :: (Ord c, Num c, Functor f, Foldable f, Alternative (PQueue t c)) => f (PQueue t c a) -> (PQueue Pruned c (a -> a), f (PQueue t c a))

-- | Imposes the given cost on the current computation branch. &gt; cost k
--   = withCost k (pure ())
cost :: (Semigroup c, Num c, Ord c) => c -> PQueue Branching c ()

-- | Returns <a>Just</a> the minimal cost present in the queue,
--   <a>Nothing</a> if the queue is empty.
leastCost :: Monoid c => PQueue t c a -> Maybe c

-- | <tt>withCost k</tt> adds a penalty of k to each value in the queue.
withCost :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a
instance GHC.Show.Show a => GHC.Show.Show (Data.PriorityQueue.Ground a)
instance (GHC.Show.Show c, GHC.Show.Show a) => GHC.Show.Show (Data.PriorityQueue.PQueue t c a)
instance Data.Foldable.Foldable (Data.PriorityQueue.PQueue t c)
instance GHC.Base.Functor (Data.PriorityQueue.PQueue t c)
instance (GHC.Base.Alternative (Data.PriorityQueue.PQueue t c), GHC.Base.Semigroup c) => GHC.Base.Applicative (Data.PriorityQueue.PQueue t c)
instance (GHC.Num.Num c, GHC.Classes.Ord c, GHC.Base.Semigroup c) => GHC.Base.Alternative (Data.PriorityQueue.PQueue Data.PriorityQueue.Branching c)
instance (GHC.Num.Num c, GHC.Classes.Ord c, GHC.Base.Semigroup c) => GHC.Base.Alternative (Data.PriorityQueue.PQueue Data.PriorityQueue.Pruned c)
instance (GHC.Base.Semigroup c, GHC.Base.Alternative (Data.PriorityQueue.PQueue t c)) => GHC.Base.Monad (Data.PriorityQueue.PQueue t c)
instance Data.Foldable.Foldable Data.PriorityQueue.Ground
instance GHC.Base.Functor Data.PriorityQueue.Ground
instance GHC.Base.Applicative Data.PriorityQueue.Ground