Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

- data PQueue t c a
- data Branching
- data Pruned
- branchable :: PQueue Pruned c a -> PQueue t c a
- prune :: PQueue t c a -> PQueue Pruned c a
- pruneAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a
- pruneAlternativesAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a
- mapWithCost :: Monoid c => (c -> a -> b) -> PQueue t c a -> PQueue t c b
- filter :: (a -> Bool) -> PQueue t c a -> PQueue t c a
- foldPeers :: (a -> a -> a) -> PQueue t c a -> PQueue t c a
- canonical :: Semigroup c => PQueue t c a -> PQueue t c a
- pruneSubsets :: (a -> b -> Maybe (a, b)) -> a -> PQueue t c b -> PQueue t c b
- strip :: (Ord c, Num c) => PQueue Pruned c a -> PQueue t c b -> PQueue t c b
- 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))
- cost :: (Semigroup c, Num c, Ord c) => c -> PQueue Branching c ()
- leastCost :: Monoid c => PQueue t c a -> Maybe c
- withCost :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a

# Documentation

A lazy-spined priority queue where the type parameters t c a are:

- t for a phantom that can be either Pruned for a single-item container or Branching for a growing priority queue;
- c for the cost type, like Sum Int; and
- a for the values

#### Instances

(Semigroup c, Alternative (PQueue t c)) => Monad (PQueue t c) Source # | |

Functor (PQueue t c) Source # | |

(Alternative (PQueue t c), Semigroup c) => Applicative (PQueue t c) Source # | |

Defined in Data.PriorityQueue | |

Foldable (PQueue t c) Source # | |

Defined in Data.PriorityQueue fold :: Monoid m => PQueue t c m -> m # foldMap :: Monoid m => (a -> m) -> PQueue t c a -> m # foldMap' :: Monoid m => (a -> m) -> PQueue t c a -> m # foldr :: (a -> b -> b) -> b -> PQueue t c a -> b # foldr' :: (a -> b -> b) -> b -> PQueue t c a -> b # foldl :: (b -> a -> b) -> b -> PQueue t c a -> b # foldl' :: (b -> a -> b) -> b -> PQueue t c a -> b # foldr1 :: (a -> a -> a) -> PQueue t c a -> a # foldl1 :: (a -> a -> a) -> PQueue t c a -> a # toList :: PQueue t c a -> [a] # null :: PQueue t c a -> Bool # length :: PQueue t c a -> Int # elem :: Eq a => a -> PQueue t c a -> Bool # maximum :: Ord a => PQueue t c a -> a # minimum :: Ord a => PQueue t c a -> a # | |

(Num c, Ord c, Semigroup c) => Alternative (PQueue Pruned c) Source # | |

(Num c, Ord c, Semigroup c) => Alternative (PQueue Branching c) Source # | |

(Show c, Show a) => Show (PQueue t c a) Source # | |

#### Instances

prune :: PQueue t c a -> PQueue Pruned c a Source #

Prune away all stored values except the one with the least penalty, making the queue `Pruned`

.

pruneAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a Source #

Prune away all stored values more expensive than the given cost.

pruneAlternativesAbove :: (Semigroup c, Num c, Ord c) => c -> PQueue t c a -> PQueue t c a Source #

Prune away all stored values more expensive than the given cost and a less expensive alternative value.

mapWithCost :: Monoid c => (c -> a -> b) -> PQueue t c a -> PQueue t c b Source #

Maps each item contained in the queue, supplying the item's cost as first argument

filter :: (a -> Bool) -> PQueue t c a -> PQueue t c a Source #

Filter away from the queue the values that the argument function maps to `False`

foldPeers :: (a -> a -> a) -> PQueue t c a -> PQueue t c a Source #

Fold together all stored values that share the same priority.

canonical :: Semigroup c => PQueue t c a -> PQueue t c a Source #

Minimize the queue structure. This operation forces the entire spine of the queue and its every level.

pruneSubsets :: (a -> b -> Maybe (a, b)) -> a -> PQueue t c b -> PQueue t c b Source #

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. > fold (pruneSubsets plusDiff mempty pq) == fold pq > where plusDiff u a > | gcd u a == a = Nothing > | d a - gcd u a = Just (u < d, d)

strip :: (Ord c, Num c) => PQueue Pruned c a -> PQueue t c b -> PQueue t c b Source #

Subtract the first argument cost GCD from the cost of every value in the second argument

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)) Source #

Returns the pair of the GCD of all the penalties and the penalties without the GCD > gcd * rest == f > where (gcd, rest) = stripCommon f

cost :: (Semigroup c, Num c, Ord c) => c -> PQueue Branching c () Source #

Imposes the given cost on the current computation branch. > cost k = withCost k (pure ())