Data.Queue.Indexed.Binomial

Size-indexed binomial heaps.

Documentation

data Tree n a

A size-indexed binomial tree.

Constructors

Root a (Node n a)

Instances

Functor (Tree rk)

Methods

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

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

Foldable (Tree rk)

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)

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)

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)

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)

Methods

rnf :: Tree rk a -> ()

type Rep1 (Tree n)

type Rep1 (Tree n) = D1 (MetaData "Tree" "Data.Queue.Indexed.Binomial" "type-indexed-queues-0.1.0.1-GPaLldpmb1Q20PpM0x8M72" 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)

type Rep (Tree n a) = D1 (MetaData "Tree" "Data.Queue.Indexed.Binomial" "type-indexed-queues-0.1.0.1-GPaLldpmb1Q20PpM0x8M72" 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

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)

Methods

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

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

Foldable (Node rk)

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)

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)

Methods

rnf :: Node rk a -> ()

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

A size-indexed binomial heap.

The implementation is similar to:

• Hinze, Ralf. “Functional Pearls: Explaining Binomial Heaps.” Journal of Functional Programming 9, no. 1 (January 1999): 93–104. doi:10.1017/S0956796899003317.
• Wasserman, Louis. “Playing with Priority Queues.” The Monad.Reader, May 12, 2010.

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

Methods

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

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

Functor (Binomial rk n)

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)

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)

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)

Methods

rnf :: Binomial rk n a -> ()