lca-0.2: O(log n) persistent on-line lowest common ancestor calculation without preprocessing with optional monoidal annotations

MaintainerEdward Kmett <>
Safe HaskellSafe-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 Source

Compressed paths using skew binary random access lists


lca :: Path a -> Path b -> Path aSource

O(log h) Compute the lowest common ancestor

empty :: Path aSource

The empty path

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

O(1) Invariant: most operations assume that the keys k are globally unique

uncons :: Path a -> Maybe (Int, a, Path a)Source


view :: Path a -> View Path aSource


null :: Path a -> BoolSource


length :: Path a -> IntSource


isAncestorOf :: Path a -> Path b -> BoolSource

O(log h) xs isAncestorOf ys holds when xs is a prefix starting at the root of path ys.

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

O(log (h - k)) to keep k elements of path of height h

drop :: Int -> Path a -> Path aSource

O(log k) to drop k elements from a path

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

toList :: Path a -> [(Int, a)]Source

fromList :: [(Int, a)] -> Path aSource

(~=) :: Path a -> Path b -> BoolSource

O(1) Compare to see if two trees have the same leaf key