type-indexed-queues-0.2.0.0: Queues with verified and unverified versions.

Safe HaskellSafe
LanguageHaskell2010

Data.Queue.Indexed.Binomial

Description

Size-indexed binomial heaps.

Synopsis

Documentation

data Tree n a Source #

A size-indexed binomial tree.

Constructors

Root a (Node n a) 

Instances

Functor (Tree rk) Source # 

Methods

fmap :: (a -> b) -> Tree rk a -> Tree rk b #

(<$) :: a -> Tree rk b -> Tree rk a #

Foldable (Tree rk) Source # 

Methods

fold :: Monoid m => Tree rk m -> m #

foldMap :: Monoid m => (a -> m) -> Tree rk a -> m #

foldr :: (a -> b -> b) -> b -> Tree rk a -> b #

foldr' :: (a -> b -> b) -> b -> Tree rk a -> b #

foldl :: (b -> a -> b) -> b -> Tree rk a -> b #

foldl' :: (b -> a -> b) -> b -> Tree rk a -> b #

foldr1 :: (a -> a -> a) -> Tree rk a -> a #

foldl1 :: (a -> a -> a) -> Tree rk a -> a #

toList :: Tree rk a -> [a] #

null :: Tree rk a -> Bool #

length :: Tree rk a -> Int #

elem :: Eq a => a -> Tree rk a -> Bool #

maximum :: Ord a => Tree rk a -> a #

minimum :: Ord a => Tree rk a -> a #

sum :: Num a => Tree rk a -> a #

product :: Num a => Tree rk a -> a #

Traversable (Tree rk) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> Tree rk a -> f (Tree rk b) #

sequenceA :: Applicative f => Tree rk (f a) -> f (Tree rk a) #

mapM :: Monad m => (a -> m b) -> Tree rk a -> m (Tree rk b) #

sequence :: Monad m => Tree rk (m a) -> m (Tree rk a) #

Generic1 (Tree n) Source # 

Associated Types

type Rep1 (Tree n :: * -> *) :: * -> * #

Methods

from1 :: Tree n a -> Rep1 (Tree n) a #

to1 :: Rep1 (Tree n) a -> Tree n a #

Generic (Tree n a) Source # 

Associated Types

type Rep (Tree n a) :: * -> * #

Methods

from :: Tree n a -> Rep (Tree n a) x #

to :: Rep (Tree n a) x -> Tree n a #

NFData a => NFData (Tree rk a) Source # 

Methods

rnf :: Tree rk a -> () #

type Rep1 (Tree n) Source # 
type Rep1 (Tree n) = D1 (MetaData "Tree" "Data.Queue.Indexed.Binomial" "type-indexed-queues-0.2.0.0-8uqeMba477nJxPUanpLvxV" False) (C1 (MetaCons "Root" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 (Node n)))))
type Rep (Tree n a) Source # 
type Rep (Tree n a) = D1 (MetaData "Tree" "Data.Queue.Indexed.Binomial" "type-indexed-queues-0.2.0.0-8uqeMba477nJxPUanpLvxV" False) (C1 (MetaCons "Root" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Node n a)))))

data Node :: Nat -> * -> * where Source #

A binomial tree, indexed by its size.

Constructors

NilN :: Node 0 a 
(:<) :: !(Tree n a) -> Node n a -> Node (1 + n) a 

Instances

Functor (Node rk) Source # 

Methods

fmap :: (a -> b) -> Node rk a -> Node rk b #

(<$) :: a -> Node rk b -> Node rk a #

Foldable (Node rk) Source # 

Methods

fold :: Monoid m => Node rk m -> m #

foldMap :: Monoid m => (a -> m) -> Node rk a -> m #

foldr :: (a -> b -> b) -> b -> Node rk a -> b #

foldr' :: (a -> b -> b) -> b -> Node rk a -> b #

foldl :: (b -> a -> b) -> b -> Node rk a -> b #

foldl' :: (b -> a -> b) -> b -> Node rk a -> b #

foldr1 :: (a -> a -> a) -> Node rk a -> a #

foldl1 :: (a -> a -> a) -> Node rk a -> a #

toList :: Node rk a -> [a] #

null :: Node rk a -> Bool #

length :: Node rk a -> Int #

elem :: Eq a => a -> Node rk a -> Bool #

maximum :: Ord a => Node rk a -> a #

minimum :: Ord a => Node rk a -> a #

sum :: Num a => Node rk a -> a #

product :: Num a => Node rk a -> a #

Traversable (Node rk) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> Node rk a -> f (Node rk b) #

sequenceA :: Applicative f => Node rk (f a) -> f (Node rk a) #

mapM :: Monad m => (a -> m b) -> Node rk a -> m (Node rk b) #

sequence :: Monad m => Node rk (m a) -> m (Node rk a) #

NFData a => NFData (Node rk a) Source # 

Methods

rnf :: Node rk a -> () #

data Binomial :: Nat -> Nat -> * -> * where Source #

A size-indexed binomial heap.

The implementation is similar to:

However invariants are more aggressively maintained, using a typechecker plugin. It is a list of binomial trees, equivalent to a binary number (stored least-significant-bit first).

Constructors

Nil :: Binomial n 0 a 
(:-) :: !(Tree z a) -> Binomial (1 + z) xs a -> Binomial z ((1 + xs) + xs) a infixr 5 
Skip :: Binomial (1 + z) (1 + xs) a -> Binomial z ((2 + xs) + xs) a 

Instances

Ord a => MeldableIndexedQueue (Binomial 0) a Source # 

Methods

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

Ord a => IndexedQueue (Binomial 0) a Source # 

Methods

empty :: Binomial 0 0 a Source #

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

singleton :: a -> Binomial 0 1 a Source #

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

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

Functor (Binomial rk n) Source # 

Methods

fmap :: (a -> b) -> Binomial rk n a -> Binomial rk n b #

(<$) :: a -> Binomial rk n b -> Binomial rk n a #

Foldable (Binomial rk n) Source # 

Methods

fold :: Monoid m => Binomial rk n m -> m #

foldMap :: Monoid m => (a -> m) -> Binomial rk n a -> m #

foldr :: (a -> b -> b) -> b -> Binomial rk n a -> b #

foldr' :: (a -> b -> b) -> b -> Binomial rk n a -> b #

foldl :: (b -> a -> b) -> b -> Binomial rk n a -> b #

foldl' :: (b -> a -> b) -> b -> Binomial rk n a -> b #

foldr1 :: (a -> a -> a) -> Binomial rk n a -> a #

foldl1 :: (a -> a -> a) -> Binomial rk n a -> a #

toList :: Binomial rk n a -> [a] #

null :: Binomial rk n a -> Bool #

length :: Binomial rk n a -> Int #

elem :: Eq a => a -> Binomial rk n a -> Bool #

maximum :: Ord a => Binomial rk n a -> a #

minimum :: Ord a => Binomial rk n a -> a #

sum :: Num a => Binomial rk n a -> a #

product :: Num a => Binomial rk n a -> a #

Traversable (Binomial rk n) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> Binomial rk n a -> f (Binomial rk n b) #

sequenceA :: Applicative f => Binomial rk n (f a) -> f (Binomial rk n a) #

mapM :: Monad m => (a -> m b) -> Binomial rk n a -> m (Binomial rk n b) #

sequence :: Monad m => Binomial rk n (m a) -> m (Binomial rk n a) #

NFData a => NFData (Binomial rk n a) Source # 

Methods

rnf :: Binomial rk n a -> () #