lca- O(log n) online lowest common ancestor calculation

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 k a Source

Compressed paths using skew binary random access lists


Functor (Path k) 
Foldable (Path k) 
Traversable (Path k) 
(Read k, Read a) => Read (Path k a) 
(Show k, Show a) => Show (Path k a) 

empty :: Path k aSource

The empty path

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

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

null :: Path k a -> BoolSource


length :: Path k a -> IntSource


isAncestorOf :: Eq k => Path k a -> Path k b -> BoolSource

lca :: Eq k => Path k a -> Path k b -> Path k aSource

O(log h) Compute the lowest common ancestor

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

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

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

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

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

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

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

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

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