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 a
- toList :: Path a -> [(Int, a)]
- fromList :: Monoid a => [(Int, a)] -> Path a
- map :: (Monoid a, Monoid b) => (a -> b) -> Path a -> Path b
- mapHom :: (a -> b) -> Path a -> Path b
- mapWithKey :: (Monoid a, 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 => Int -> Path a -> (a, Path a)
- drop :: Monoid a => Int -> Path a -> Path a
- mdrop :: Monoid a => Int -> Path a -> (a, Path a)
- (~=) :: Path a -> Path b -> Bool
- lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path a
- mlca :: (Monoid a, Monoid b) => Path a -> Path b -> (a, Path a, b, Path b)

# Documentation

Compressed paths using skew binary random access lists

mapHom :: (a -> b) -> Path a -> Path bSource

`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

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

cons :: Monoid a => Int -> a -> Path a -> Path aSource

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

are globally unique

keep :: Monoid a => Int -> Path a -> Path aSource

*O(log (h - k))* to `keep k`

elements of path of height `h`

mkeep :: Monoid a => Int -> Path a -> (a, Path a)Source

*O(log (h - k))* to `keep k`

elements of path of height `h`

, and provide a monoidal summary of the dropped elements

mdrop :: Monoid a => Int -> Path a -> (a, Path a)Source

*O(log k)* to `drop k`

elements from a path and provide a monoidal summary of the dropped elements