Portability | portable |
---|---|
Stability | experimental |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Safe Haskell | Safe-Infered |
Provides online calculation of the the lowest common ancestor in O(log h) by compressing the spine of the paths using a skew binary random access list.
Algorithms used here assume that the key values chosen for k
are
globally unique.
- data Path k a
- empty :: Path k a
- cons :: k -> a -> Path k a -> Path k a
- null :: Path k a -> Bool
- length :: Path k a -> Int
- isAncestorOf :: Eq k => Path k a -> Path k b -> Bool
- lca :: Eq k => Path k a -> Path k b -> Path k a
- keep :: Int -> Path k a -> Path k a
- drop :: Int -> Path k a -> Path k a
- traverseWithKey :: Applicative f => (k -> a -> f b) -> Path k a -> f (Path k b)
- toList :: Path k a -> [(k, a)]
- fromList :: [(k, a)] -> Path k a
- (~=) :: Eq k => Path k a -> Path k b -> Bool
Documentation
Compressed paths using skew binary random access lists
cons :: k -> a -> Path k a -> Path k aSource
O(1) Invariant: most operations assume that the keys k
are globally unique
traverseWithKey :: Applicative f => (k -> a -> f b) -> Path k a -> f (Path k b)Source