Data.LCA.Online.Monoidal

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.

Documentation

data Path a

A compressed Path as a skew binary random access list

Instances

Foldable Path

Defined in Data.LCA.Online.Monoidal

Methods

fold :: Monoid m => Path m -> m

foldMap :: Monoid m => (a -> m) -> Path a -> m

foldMap' :: Monoid m => (a -> m) -> Path a -> m

foldr :: (a -> b -> b) -> b -> Path a -> b

foldr' :: (a -> b -> b) -> b -> Path a -> b

foldl :: (b -> a -> b) -> b -> Path a -> b

foldl' :: (b -> a -> b) -> b -> Path a -> b

foldr1 :: (a -> a -> a) -> Path a -> a

foldl1 :: (a -> a -> a) -> Path a -> a

toList :: Path a -> [a]

null :: Path a -> Bool

length :: Path a -> Int

elem :: Eq a => a -> Path a -> Bool

maximum :: Ord a => Path a -> a

minimum :: Ord a => Path a -> a

sum :: Num a => Path a -> a

product :: Num a => Path a -> a

Read a => Read (Path a)

Defined in Data.LCA.Online.Monoidal

Methods

readsPrec :: Int -> ReadS (Path a)

readList :: ReadS [Path a]

readPrec :: ReadPrec (Path a)

readListPrec :: ReadPrec [Path a]

Show a => Show (Path a)

Defined in Data.LCA.Online.Monoidal

Methods

showsPrec :: Int -> Path a -> ShowS

show :: Path a -> String

showList :: [Path a] -> ShowS

toList :: Path a -> [(Int, a)]

Convert a Path to a list of (ID, value) pairs.

fromList :: Monoid a => [(Int, a)] -> Path a

Build a Path from a list of (ID, value) pairs.

map :: Monoid b => (a -> b) -> Path a -> Path b

O(n) Re-annotate a Path full of monoidal values using a different Monoid.

mapHom :: (a -> b) -> Path a -> Path b

O(n) Re-annotate a Path full of monoidal values/

Unlike map, mapHom f assumes that f is a Monoid homomorphism, that is to say you must ensure

f a `mappend` f b = f (a `mappend` b)
f mempty = mempty

mapWithKey :: Monoid b => (Int -> a -> b) -> Path a -> Path b

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)

Traverse a Path yielding a new monoidal annotation.

traverseWithKey :: (Applicative f, Monoid b) => (Int -> a -> f b) -> Path a -> f (Path b)

Traverse a Path with access to the node IDs.

empty :: Path a

The empty Path

cons :: Monoid a => Int -> a -> Path a -> Path a

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)

O(1) Extract the node ID and value from the newest node on the Path.

view :: Monoid a => Path a -> View Path a

O(1) Extract the node ID and value from the newest node on the Path, slightly faster than uncons.

null :: Path a -> Bool

O(1) Returns True iff the path is empty.

length :: Path a -> Int

O(1) Determine the length of a Path.

measure :: Monoid a => Path a -> a

Extract a monoidal summary of a Path.

isAncestorOf :: Monoid b => Path a -> Path b -> Bool

O(log h) xs `isAncestorOf` ys holds when xs is a prefix starting at the root of path ys.

keep :: Monoid a => Int -> Path a -> Path a

O(log (h - k)) to keep k elements of Path of length h

This solves the online version of the "level ancestor problem" with no preprocessing in O(log h) time, improving known complexity bounds.

http://en.wikipedia.org/wiki/Level_ancestor_problem

mkeep :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, Path a)

O(log (h - k)) to keep k elements of Path of length h, and provide a monoidal summary of the dropped elements using a supplied monoid homomorphism.

drop :: Monoid a => Int -> Path a -> Path a

O(log k) to drop k elements from a Path

mdrop :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, Path a)

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

O(1) Compare to see if two trees have the same root key

lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path a

O(log h) Compute the lowest common ancestor of two paths

>>> let fromList' = fromList . fmap (flip (,) ())
>>> length (lca (fromList' [1, 2, 3, 4, 5, 6]) (fromList' [7, 8, 3, 4, 5, 6]))
4

mlca :: (Monoid a, Monoid b, Monoid c, Monoid d) => (a -> c) -> (b -> d) -> Path a -> Path b -> (c, Path a, d, Path b)

O(log h) Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails using the supplied monoid homomorphisms.