Portability | portable |
---|---|

Stability | experimental |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Safe Haskell | Safe-Infered |

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.

Algorithms used here assume that the key values chosen for `k`

are
globally unique.

- data Path k a
- empty :: Path k a
- cons :: k -> a -> Path k a -> Path k a
- null :: Path k a -> Bool
- length :: Path k a -> Int
- isAncestorOf :: Eq k => Path k a -> Path k b -> Bool
- lca :: Eq k => Path k a -> Path k b -> Path k a
- keep :: Int -> Path k a -> Path k a
- drop :: Int -> Path k a -> Path k a
- traverseWithKey :: Applicative f => (k -> a -> f b) -> Path k a -> f (Path k b)
- toList :: Path k a -> [(k, a)]
- fromList :: [(k, a)] -> Path k a
- (~=) :: Eq k => Path k a -> Path k b -> Bool

# Documentation

Compressed paths using skew binary random access lists

cons :: k -> a -> Path k a -> Path k aSource

*O(1)* Invariant: most operations assume that the keys `k`

are globally unique

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