Copyright | (C) 2011-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 |

Naive online calculation of the the lowest common ancestor in *O(h)*

## Synopsis

- data 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
- lca :: Path a -> Path b -> Path a
- 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

An uncompressed `Path`

with memoized length.

#### Instances

Functor Path Source # | |

Foldable Path Source # | |

Defined in Data.LCA.Online.Naive 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 # | |

Traversable Path Source # | |

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

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

cons :: 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 :: Path a -> Maybe (Int, a, Path a) Source #

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

.

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

*O(h)* `xs `

holds when `isAncestorOf`

ys`xs`

is a prefix starting at the root of `Path`

`ys`

.

lca :: Path a -> Path b -> Path a Source #

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

`>>>`

`let fromList' = fromList . map (flip (,) ())`

`>>>`

4`length (lca (fromList' [1, 2, 3, 4, 5, 6]) (fromList' [7, 8, 3, 4, 5, 6]))`

traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) Source #

Traverse a `Path`

with access to the node IDs.