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

Safe HaskellSafe
LanguageHaskell2010

Data.Queue.Indexed.Braun

Description

Type-indexed Braun heaps.

Synopsis

Documentation

data Braun n a where Source #

A Braun heap. Somewhat based on this implementation, but with a different strategy for maintaining invariants.

A braun tree is one where every left branch has at most one more element than the right branch.

Constructors

Leaf :: Braun 0 a 
Node :: !(Offset n m) -> a -> Braun n a -> Braun m a -> Braun ((n + m) + 1) a 

Instances

Ord a => IndexedQueue Braun a Source # 

Methods

empty :: Braun 0 a Source #

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

singleton :: a -> Braun 1 a Source #

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

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

NFData a => NFData (Braun n a) Source # 

Methods

rnf :: Braun n a -> () #

data Offset n m where Source #

The "singleton" for whether or not the left branch is larger than the right.

Constructors

Even :: Offset n n 
Lean :: Offset (1 + n) n 

Instances

NFData (Offset n m) Source # 

Methods

rnf :: Offset n m -> () #