Copyright | (C) 2012-2015 Edward Kmett |
---|---|
License | BSD-style (see the file LICENSE) |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Stability | experimental |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell98 |
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.
This library implements the technique described in my talk
http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search
to improve the known asymptotic bounds on both online lowest common ancestor search
http://en.wikipedia.org/wiki/Lowest_common_ancestor
and the online level ancestor problem:
http://en.wikipedia.org/wiki/Level_ancestor_problem
Algorithms used here assume that the key values chosen for k
are
globally unique.
This version provides access to a monoidal "summary" of the elided path for many operations.
- data Path a
- toList :: Path a -> [(Int, a)]
- fromList :: Monoid a => [(Int, a)] -> Path a
- map :: Monoid b => (a -> b) -> Path a -> Path b
- mapHom :: (a -> b) -> Path a -> Path b
- mapWithKey :: Monoid b => (Int -> a -> b) -> Path a -> Path b
- traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b)
- traverseWithKey :: (Applicative f, Monoid b) => (Int -> a -> f b) -> Path a -> f (Path b)
- empty :: Path a
- cons :: Monoid a => Int -> a -> Path a -> Path a
- uncons :: Monoid a => Path a -> Maybe (Int, a, Path a)
- view :: Monoid a => Path a -> View Path a
- null :: Foldable t => forall a. t a -> Bool
- length :: Foldable t => forall a. t a -> Int
- measure :: Monoid a => Path a -> a
- isAncestorOf :: Monoid b => Path a -> Path b -> Bool
- keep :: Monoid a => Int -> Path a -> Path a
- mkeep :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, Path a)
- drop :: Monoid a => Int -> Path a -> Path a
- mdrop :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, Path a)
- (~=) :: Path a -> Path b -> Bool
- lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path a
- mlca :: (Monoid a, Monoid b, Monoid c, Monoid d) => (a -> c) -> (b -> d) -> Path a -> Path b -> (c, Path a, d, Path b)
Documentation
A compressed Path
as a skew binary random access list
mapWithKey :: Monoid b => (Int -> a -> b) -> Path a -> Path b Source #
O(n) Re-annotate a Path
full of monoidal values with access to the key.
traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b) Source #
Traverse a Path
yielding a new monoidal annotation.
traverseWithKey :: (Applicative f, Monoid b) => (Int -> a -> f b) -> Path a -> f (Path b) Source #
Traverse a Path
with access to the node IDs.
cons :: Monoid a => Int -> a -> Path a -> Path a Source #
O(1) Invariant: most operations assume that the keys k
are globally unique
Extend the Path
with a new node ID and value.
uncons :: Monoid a => Path a -> Maybe (Int, a, Path a) Source #
O(1) Extract the node ID and value from the newest node on the Path
.
null :: Foldable t => forall a. t a -> Bool #
Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.
length :: Foldable t => forall a. t a -> Int #
Returns the size/length of a finite structure as an Int
. The
default implementation is optimized for structures that are similar to
cons-lists, because there is no general way to do better.
isAncestorOf :: Monoid b => Path a -> Path b -> Bool Source #
O(log h) xs `
holds when isAncestorOf'
ysxs
is a prefix starting at the root of path ys
.
mdrop :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, Path a) Source #
O(log k) to drop k
elements from a Path
and provide a monoidal summary of the dropped elements
using a suplied monoid homomorphism
(~=) :: Path a -> Path b -> Bool infix 4 Source #
O(1) Compare to see if two trees have the same leaf key