Data.Queue.Class

Classes for the various heaps, mainly to avoid name clashing.

Documentation

class Queue h a where

A class for queues. Conforming members can have their own definition of order on their contents. (i.e., Ord is not required)

Minimal complete definition

minView, insert, empty

Methods

minView :: h a -> Maybe (a, h a)

Return the first element, and the remaining elements, or Nothing if the queue is empty. For most queues, this will be the minimal element

insert :: a -> h a -> h a

Insert an element into the queue.

empty :: h a

The empty queue.

singleton :: a -> h a

A queue with one element.

toList :: h a -> [a]

Return a list of the contents of the queue, in order, from smallest to largest.

fromList :: [a] -> h a

Create a heap from a list.

heapSort :: p h -> [a] -> [a]

Perform heap sort on a list of items.

Instances

Queue [] a

Methods

minView :: [a] -> Maybe (a, [a])

insert :: a -> [a] -> [a]

empty :: [a]

singleton :: a -> [a]

toList :: [a] -> [a]

fromList :: [a] -> [a]

heapSort :: p [] -> [a] -> [a]

Ord a => Queue Set a

Methods

minView :: Set a -> Maybe (a, Set a)

insert :: a -> Set a -> Set a

empty :: Set a

singleton :: a -> Set a

toList :: Set a -> [a]

fromList :: [a] -> Set a

heapSort :: p Set -> [a] -> [a]

Ord a => Queue Leftist a

Methods

minView :: Leftist a -> Maybe (a, Leftist a)

insert :: a -> Leftist a -> Leftist a

empty :: Leftist a

singleton :: a -> Leftist a

toList :: Leftist a -> [a]

fromList :: [a] -> Leftist a

heapSort :: p Leftist -> [a] -> [a]

Ord a => Queue Pairing a

Methods

minView :: Pairing a -> Maybe (a, Pairing a)

insert :: a -> Pairing a -> Pairing a

empty :: Pairing a

singleton :: a -> Pairing a

toList :: Pairing a -> [a]

fromList :: [a] -> Pairing a

heapSort :: p Pairing -> [a] -> [a]

Ord a => Queue Braun a

Methods

minView :: Braun a -> Maybe (a, Braun a)

insert :: a -> Braun a -> Braun a

empty :: Braun a

singleton :: a -> Braun a

toList :: Braun a -> [a]

fromList :: [a] -> Braun a

heapSort :: p Braun -> [a] -> [a]

Ord a => Queue Skew a

Methods

minView :: Skew a -> Maybe (a, Skew a)

insert :: a -> Skew a -> Skew a

empty :: Skew a

singleton :: a -> Skew a

toList :: Skew a -> [a]

fromList :: [a] -> Skew a

heapSort :: p Skew -> [a] -> [a]

Ord a => Queue Splay a

Methods

minView :: Splay a -> Maybe (a, Splay a)

insert :: a -> Splay a -> Splay a

empty :: Splay a

singleton :: a -> Splay a

toList :: Splay a -> [a]

fromList :: [a] -> Splay a

heapSort :: p Splay -> [a] -> [a]

IndexedQueue h a => Queue (ErasedSize h) a

Methods

minView :: ErasedSize h a -> Maybe (a, ErasedSize h a)

insert :: a -> ErasedSize h a -> ErasedSize h a

empty :: ErasedSize h a

singleton :: a -> ErasedSize h a

toList :: ErasedSize h a -> [a]

fromList :: [a] -> ErasedSize h a

heapSort :: p (ErasedSize h) -> [a] -> [a]

Queue f a => Queue (WithDict f) a

Methods

minView :: WithDict f a -> Maybe (a, WithDict f a)

insert :: a -> WithDict f a -> WithDict f a

empty :: WithDict f a

singleton :: a -> WithDict f a

toList :: WithDict f a -> [a]

fromList :: [a] -> WithDict f a

heapSort :: p (WithDict f) -> [a] -> [a]

Ord a => Queue (Binomial Z) a

Methods

minView :: Binomial Z a -> Maybe (a, Binomial Z a)

insert :: a -> Binomial Z a -> Binomial Z a

empty :: Binomial Z a

singleton :: a -> Binomial Z a

toList :: Binomial Z a -> [a]

fromList :: [a] -> Binomial Z a

heapSort :: p (Binomial Z) -> [a] -> [a]

class Queue h a => MeldableQueue h a where

A class for meldable queues. Conforming members should form a monoid under merge and empty.

Minimal complete definition

merge

Methods

merge :: h a -> h a -> h a

Merge two heaps. This operation is associative, and has the identity of empty.

merge x (merge y z) = merge (merge x y) z

merge x empty = merge empty x = x

fromFoldable :: Foldable f => f a -> h a

Create a heap from a Foldable container. This operation is provided to allow the use of foldMap, which may be asymptotically more efficient. The default definition uses foldMap.

Instances

MeldableQueue [] a

Methods

merge :: [a] -> [a] -> [a]

fromFoldable :: Foldable f => f a -> [a]

Ord a => MeldableQueue Set a

Methods

merge :: Set a -> Set a -> Set a

fromFoldable :: Foldable f => f a -> Set a

Ord a => MeldableQueue Leftist a

Methods

merge :: Leftist a -> Leftist a -> Leftist a

fromFoldable :: Foldable f => f a -> Leftist a

Ord a => MeldableQueue Pairing a

Methods

merge :: Pairing a -> Pairing a -> Pairing a

fromFoldable :: Foldable f => f a -> Pairing a

Ord a => MeldableQueue Skew a

Methods

merge :: Skew a -> Skew a -> Skew a

fromFoldable :: Foldable f => f a -> Skew a

Ord a => MeldableQueue Splay a

Methods

merge :: Splay a -> Splay a -> Splay a

fromFoldable :: Foldable f => f a -> Splay a

MeldableIndexedQueue h a => MeldableQueue (ErasedSize h) a

Methods

merge :: ErasedSize h a -> ErasedSize h a -> ErasedSize h a

fromFoldable :: Foldable f => f a -> ErasedSize h a

MeldableQueue f a => MeldableQueue (WithDict f) a

Methods

merge :: WithDict f a -> WithDict f a -> WithDict f a

fromFoldable :: Foldable f => f a -> WithDict f a

Ord a => MeldableQueue (Binomial Z) a

Methods

merge :: Binomial Z a -> Binomial Z a -> Binomial Z a

fromFoldable :: Foldable f => f a -> Binomial Z a

showsPrecQueue :: (Queue h a, Show a) => Int -> h a -> ShowS

A default definition for showsPrec.

readPrecQueue :: (Read a, Queue h a) => Int -> ReadS (h a)

A default definition for readsPrec.

eqQueue :: (Eq a, Queue h a) => h a -> h a -> Bool

A default definition of ==.

cmpQueue :: (Ord a, Queue h a) => h a -> h a -> Ordering

A default definition of compare.