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 |

Language | Haskell98 |

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

- 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 :: Foldable t => forall a. t a -> Bool
- length :: Foldable t => forall a. t 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.

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`

.

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 :: Path a -> Path b -> Bool Source #

*O(h)* `xs `

holds when `isAncestorOf`

ys`xs`

is a prefix starting at the root of `Path`

`ys`

.

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

Traverse a `Path`

with access to the node IDs.