lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing

MaintainerEdward Kmett <>
Safe HaskellSafe-Inferred



Provides online calculation of the the lowest common ancestor in O(log h) by compressing the spine of a Path using a skew-binary random access list.

This library implements the technique described in my talk

to improve the known asymptotic bounds on both online lowest common ancestor search

and the online level ancestor problem:

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 of two paths.

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

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.

view :: Path a -> View Path aSource

O(1) Extract the node ID and value from the newest node on the Path, slightly faster than uncons.

null :: Path a -> BoolSource

O(1) Returns True iff the path is empty.

length :: Path a -> IntSource

O(1) Determine the length of a Path.

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 length h

This solves the online version of the "level ancestor problem" with no preprocessing in O(log h) time, improving known complexity bounds.

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

Traverse a Path with access to the node IDs.

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

Convert a Path to a list of (ID, value) pairs.

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

Build a Path from a list of (ID, value) pairs.

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

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