Portability | non-portable |
---|---|
Stability | experimental |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Safe Haskell | None |
Bootstrapped catenable non-empty pairing heaps as described in
https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-5
- data Heap a = Heap !Key a [Heap a] [Heap a] [Heap a]
- fby :: Heap a -> Heap a -> Heap a
- mix :: Heap a -> Heap a -> Heap a
- singleton :: Key -> a -> Heap a
- head :: Heap a -> (Key, a)
- tail :: Heap a -> Maybe (Heap a)
- fromList :: [(Key, a)] -> Heap a
- fromAscList :: [(Key, a)] -> Heap a
- streamHeapWith :: Monad m => (a -> a -> a) -> Maybe (Heap a) -> Stream m (Key, a)
- streamHeapWith0 :: Monad m => (a -> a -> Maybe a) -> Maybe (Heap a) -> Stream m (Key, a)
Documentation
Bootstrapped catenable non-empty pairing heaps
fby :: Heap a -> Heap a -> Heap aSource
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 aSource
Interleave two heaps making a new Heap
>>>
head $ singleton (Key 1 1) 1 `mix` singleton (Key 2 2) 2
(Key 1 1,1)
fromAscList :: [(Key, a)] -> Heap aSource
Build a Heap
from an list of elements that must be in strictly ascending Morton order.