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 a
- lca :: Path a -> Path b -> Path a
- empty :: Path a
- cons :: Int -> a -> Path a -> Path a
- uncons :: Path a -> Maybe (Int, a, Path a)
- view :: Path a -> View Path a
- null :: Path a -> Bool
- length :: Path a -> Int
- isAncestorOf :: Path a -> Path b -> Bool
- keep :: Int -> Path a -> Path a
- drop :: Int -> Path a -> Path a
- traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)
- toList :: Path a -> [(Int, a)]
- fromList :: [(Int, a)] -> Path a
- (~=) :: Path a -> Path b -> Bool
Documentation
Compressed paths using skew binary random access lists
cons :: Int -> a -> Path a -> Path aSource
O(1) Invariant: most operations assume that the keys k
are globally unique
isAncestorOf :: Path a -> Path b -> BoolSource
O(log h) xs
holds when isAncestorOf
ysxs
is a prefix starting at the root of path ys
.
traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)Source