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-Inferred |

Language | Haskell2010 |

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

- 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 :: Path a -> Bool
- length :: Path 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

#### Instances

Foldable Path Source # | |

Defined in Data.LCA.Online.Monoidal 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 # elem :: Eq a => a -> Path a -> Bool # maximum :: Ord a => Path a -> a # | |

Read a => Read (Path a) Source # | |

Show a => Show (Path a) Source # | |

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`

.

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

*O(log h)* `xs ``

holds when `isAncestorOf`

` ys`xs`

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