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

Data.LCA.Online.Monoidal

Description

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.

Synopsis

Documentation

data Path a #

A compressed Path as a skew binary random access list

Instances

Foldable Path #
Methods fold :: Monoid m => Path m -> 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) #
Methods readsPrec :: Int -> ReadS (Path a) # readList :: ReadS [Path a] # readPrec :: ReadPrec (Path a) # readListPrec :: ReadPrec [Path a] #
Show a => Show (Path a) #
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 :: 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.

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 leaf key

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

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

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.