Sparse.Matrix.Internal.Heap

Bootstrapped catenable non-empty pairing heaps as described in

https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-5

Documentation

data Heap a

Bootstrapped _catenable_ non-empty pairing heaps

Constructors

Heap !Key a [Heap a] [Heap a] [Heap a]

Instances

Functor Heap

Foldable Heap

Traversable Heap

FunctorWithIndex Key Heap

FoldableWithIndex Key Heap

TraversableWithIndex Key Heap

Read a => Read (Heap a)

Show a => Show (Heap a)

fby :: Heap a -> Heap a -> Heap a

Append two heaps where we know every key in the first occurs before every key in the second

>>> head $ singleton (Key 1 1) 1 `fby` singleton (Key 2 2) 2
(Key 1 1,1)

mix :: Heap a -> Heap a -> Heap a

Interleave two heaps making a new Heap

>>> head $ singleton (Key 1 1) 1 `mix` singleton (Key 2 2) 2
(Key 1 1,1)

singleton :: Key -> a -> Heap a

>>> singleton (Key 1 1) 1
Heap (Key 1 1) 1 [] [] []

head :: Heap a -> (Key, a)

>>> head $ singleton (Key 1 1) 1
(Key 1 1,1)

tail :: Heap a -> Maybe (Heap a)

>>> tail $ singleton (Key 1 1) 1
Nothing

fromList :: [(Key, a)] -> Heap a

Build a Heap from a jumbled up list of elements.

fromAscList :: [(Key, a)] -> Heap a

Build a Heap from an list of elements that must be in strictly ascending Morton order.

streamHeapWith :: Monad m => (a -> a -> a) -> Maybe (Heap a) -> Stream m (Key, a)

Convert a Heap into a Stream folding together values with identical keys using the supplied addition operator.

streamHeapWith0 :: Monad m => (a -> a -> Maybe a) -> Maybe (Heap a) -> Stream m (Key, a)

Convert a Heap into a Stream folding together values with identical keys using the supplied addition operator that is allowed to return a sparse 0, by returning Nothing.

timesSingleton :: (a -> b -> c) -> Stream Id (Key, a) -> Key -> b -> Maybe (Heap c)

This is an internal Heap fusion combinator used to multiply on the right by a singleton Key/value pair.

singletonTimes :: (a -> b -> c) -> Key -> a -> Stream Id (Key, b) -> Maybe (Heap c)

This is an internal Heap fusion combinator used to multiply on the right by a singleton Key/value pair.