Data.Queue.Indexed.Class

Classes for common functions between the heaps.

Documentation

class IndexedQueue h a where

A classed for indexed priority queues. Equivalent to Queue except the queues are indexed by their sizes.

Minimal complete definition

insert, empty, minViewMay, minView

Methods

empty :: h 0 a

The empty queue

minView :: h (1 + n) a -> (a, h n a)

Return the minimal element, and the rest of the queue.

singleton :: a -> h 1 a

A queue with one element.

insert :: a -> h n a -> h (1 + n) a

Add an element to the queue.

minViewMay :: h n a -> (n ~ 0 => b) -> (forall m. (1 + m) ~ n => a -> h m a -> b) -> b

Pattern match on the queue, and provide a proof that it is/isn't empty to the caller.

Instances

Ord a => IndexedQueue Leftist a

Methods

empty :: Leftist 0 a

minView :: Leftist (1 + n) a -> (a, Leftist n a)

singleton :: a -> Leftist 1 a

insert :: a -> Leftist n a -> Leftist (1 + n) a

minViewMay :: Leftist n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Leftist m a -> b) -> b

Ord a => IndexedQueue Pairing a

Methods

empty :: Pairing 0 a

minView :: Pairing (1 + n) a -> (a, Pairing n a)

singleton :: a -> Pairing 1 a

insert :: a -> Pairing n a -> Pairing (1 + n) a

minViewMay :: Pairing n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Pairing m a -> b) -> b

Ord a => IndexedQueue Skew a

Methods

empty :: Skew 0 a

minView :: Skew (1 + n) a -> (a, Skew n a)

singleton :: a -> Skew 1 a

insert :: a -> Skew n a -> Skew (1 + n) a

minViewMay :: Skew n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Skew m a -> b) -> b

IndexedQueue DiffList a

Methods

empty :: DiffList 0 a

minView :: DiffList (1 + n) a -> (a, DiffList n a)

singleton :: a -> DiffList 1 a

insert :: a -> DiffList n a -> DiffList (1 + n) a

minViewMay :: DiffList n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> DiffList m a -> b) -> b

IndexedQueue List a

Methods

empty :: List 0 a

minView :: List (1 + n) a -> (a, List n a)

singleton :: a -> List 1 a

insert :: a -> List n a -> List (1 + n) a

minViewMay :: List n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> List m a -> b) -> b

Ord a => IndexedQueue Braun a

Methods

empty :: Braun 0 a

minView :: Braun (1 + n) a -> (a, Braun n a)

singleton :: a -> Braun 1 a

insert :: a -> Braun n a -> Braun (1 + n) a

minViewMay :: Braun n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Braun m a -> b) -> b

Ord a => IndexedQueue (Binomial 0) a

Methods

empty :: Binomial 0 0 a

minView :: Binomial 0 (1 + n) a -> (a, Binomial 0 n a)

singleton :: a -> Binomial 0 1 a

insert :: a -> Binomial 0 n a -> Binomial 0 (1 + n) a

minViewMay :: Binomial 0 n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Binomial 0 m a -> b) -> b

class IndexedQueue h a => MeldableIndexedQueue h a where

Queues which can be merged. Conforming members should form a monoid under merge and empty.

Minimal complete definition

merge

Methods

merge :: h n a -> h m a -> h (n + m) 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

Instances

Ord a => MeldableIndexedQueue Leftist a

Methods

merge :: Leftist n a -> Leftist m a -> Leftist (n + m) a

Ord a => MeldableIndexedQueue Pairing a

Methods

merge :: Pairing n a -> Pairing m a -> Pairing (n + m) a

Ord a => MeldableIndexedQueue Skew a

Methods

merge :: Skew n a -> Skew m a -> Skew (n + m) a

MeldableIndexedQueue DiffList a

Performs merging in reverse order.

Methods

merge :: DiffList n a -> DiffList m a -> DiffList (n + m) a

MeldableIndexedQueue List a

Methods

merge :: List n a -> List m a -> List (n + m) a

Ord a => MeldableIndexedQueue (Binomial 0) a

Methods

merge :: Binomial 0 n a -> Binomial 0 m a -> Binomial 0 (n + m) a