Data.Tree.AVL.List

List related utilities for AVL trees.

Converting AVL trees to Lists (fixed element order).

These functions are lazy and allow normal lazy list processing style to be used (without necessarily converting the entire tree to a list in one gulp).

asListL :: AVL e -> [e]

List AVL tree contents in left to right order. The resulting list in ascending order if the tree is sorted.

Complexity: O(n)

toListL :: AVL e -> [e] -> [e]

Join the AVL tree contents to an existing list in left to right order. This is a ++ free function which behaves as if defined thusly..

 avl `toListL` as = (asListL avl) ++ as 

Complexity: O(n)

asListR :: AVL e -> [e]

List AVL tree contents in right to left order. The resulting list in descending order if the tree is sorted.

Complexity: O(n)

toListR :: AVL e -> [e] -> [e]

Join the AVL tree contents to an existing list in right to left order. This is a ++ free function which behaves as if defined thusly..

 avl `toListR` as = (asListR avl) ++ as 

Complexity: O(n)

Converting Lists to AVL trees (fixed element order).

asTreeLenL :: Int -> [e] -> AVL e

Convert a list of known length into an AVL tree, such that the head of the list becomes the leftmost tree element. The resulting tree is flat (and also sorted if the supplied list is sorted in ascending order).

If the actual length of the list is not the same as the supplied length then an error will be raised.

Complexity: O(n)

asTreeL :: [e] -> AVL e

As asTreeLenL, except the length of the list is calculated internally, not supplied as an argument.

Complexity: O(n)

asTreeLenR :: Int -> [e] -> AVL e

Convert a list of known length into an AVL tree, such that the head of the list becomes the rightmost tree element. The resulting tree is flat (and also sorted if the supplied list is sorted in descending order).

If the actual length of the list is not the same as the supplied length then an error will be raised.

Complexity: O(n)

asTreeR :: [e] -> AVL e

As asTreeLenR, except the length of the list is calculated internally, not supplied as an argument.

Complexity: O(n)

Converting unsorted Lists to sorted AVL trees.

genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e

Invokes genPushList on the empty AVL tree.

Complexity: O(n.(log n))

Pushing unsorted Lists in sorted AVL trees.

genPushList :: (e -> e -> COrdering e) -> AVL e -> [e] -> AVL e

Push the elements of an unsorted List in a sorted AVL tree using the supplied combining comparison.

Complexity: O(n.(log (m+n))) where n is the list length, m is the tree size.

Some analogues of common List functions.

reverseAVL :: AVL e -> AVL e

Reverse an AVL tree (swaps and reverses left and right sub-trees). The resulting tree is the mirror image of the original.

Complexity: O(n)

mapAVL :: (a -> b) -> AVL a -> AVL b

Apply a function to every element in an AVL tree. This function preserves the tree shape. There is also a strict version of this function (mapAVL').

N.B. If the tree is sorted the result of this operation will only be sorted if the applied function preserves ordering (for some suitable ordering definition).

Complexity: O(n)

mapAVL' :: (a -> b) -> AVL a -> AVL b

Similar to mapAVL, but the supplied function is applied strictly.

Complexity: O(n)

traverseAVL :: Applicative f => (a -> f b) -> AVL a -> f (AVL b)

replicateAVL :: Int -> e -> AVL e

Construct a flat AVL tree of size n (n>=0), where all elements are identical.

Complexity: O(log n)

filterViaList :: (e -> Bool) -> AVL e -> AVL e

Remove all AVL tree elements which do not satisfy the supplied predicate. Element ordering is preserved. The resulting tree is flat.

Complexity: O(n)

mapMaybeViaList :: (a -> Maybe b) -> AVL a -> AVL b

Remove all AVL tree elements for which the supplied function returns Nothing. Element ordering is preserved. The resulting tree is flat.

Complexity: O(n)

partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)

Partition an AVL tree using the supplied predicate. The first AVL tree in the resulting pair contains all elements for which the predicate is True, the second contains all those for which the predicate is False. Element ordering is preserved. Both of the resulting trees are flat.

Complexity: O(n)

Folds

Note that unlike folds over lists (foldr and foldl), there is no significant difference between left and right folds in AVL trees, other than which side of the tree each starts with. Both involve tail and non-tail recursion. Therefore this library provides strict and lazy versions of both.

foldrAVL :: (e -> a -> a) -> a -> AVL e -> a

The AVL equivalent of foldr on lists. This is a the lazy version (as lazy as the folding function anyway). Using this version with a function that is strict in it's second argument will result in O(n) stack use. See foldrAVL' for a strict version.

It behaves as if defined..

 foldrAVL f a avl = foldr f a (asListL avl)

For example, the asListL function could be defined..

 asListL = foldrAVL (:) []

Complexity: O(n)

foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a

The strict version of foldrAVL, which is useful for functions which are strict in their second argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

foldr1AVL :: (e -> e -> e) -> AVL e -> e

The AVL equivalent of foldr1 on lists. This is a the lazy version (as lazy as the folding function anyway). Using this version with a function that is strict in it's second argument will result in O(n) stack use. See foldr1AVL' for a strict version.

 foldr1AVL f avl = foldr1 f (asListL avl)

This function raises an error if the tree is empty.

Complexity: O(n)

foldr1AVL' :: (e -> e -> e) -> AVL e -> e

The strict version of foldr1AVL, which is useful for functions which are strict in their second argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a

This fold is a hybrid between foldrAVL and foldr1AVL. As with foldr1AVL, it requires a non-empty tree, but instead of treating the rightmost element as an initial value, it applies a function to it (second function argument) and uses the result instead. This allows a more flexible type for the main folding function (same type as that used by foldrAVL). As with foldrAVL and foldr1AVL, this function is lazy, so it's best not to use it with functions that are strict in their second argument. See foldr2AVL' for a strict version.

Complexity: O(n)

foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a

The strict version of foldr2AVL, which is useful for functions which are strict in their second argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

foldlAVL :: (a -> e -> a) -> a -> AVL e -> a

The AVL equivalent of foldl on lists. This is a the lazy version (as lazy as the folding function anyway). Using this version with a function that is strict in it's first argument will result in O(n) stack use. See foldlAVL' for a strict version.

 foldlAVL f a avl = foldl f a (asListL avl)

For example, the asListR function could be defined..

 asListR = foldlAVL (flip (:)) []

Complexity: O(n)

foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a

The strict version of foldlAVL, which is useful for functions which are strict in their first argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

foldl1AVL :: (e -> e -> e) -> AVL e -> e

The AVL equivalent of foldl1 on lists. This is a the lazy version (as lazy as the folding function anyway). Using this version with a function that is strict in it's first argument will result in O(n) stack use. See foldl1AVL' for a strict version.

 foldl1AVL f avl = foldl1 f (asListL avl)

This function raises an error if the tree is empty.

Complexity: O(n)

foldl1AVL' :: (e -> e -> e) -> AVL e -> e

The strict version of foldl1AVL, which is useful for functions which are strict in their first argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a

This fold is a hybrid between foldlAVL and foldl1AVL. As with foldl1AVL, it requires a non-empty tree, but instead of treating the leftmost element as an initial value, it applies a function to it (second function argument) and uses the result instead. This allows a more flexible type for the main folding function (same type as that used by foldlAVL). As with foldlAVL and foldl1AVL, this function is lazy, so it's best not to use it with functions that are strict in their first argument. See foldl2AVL' for a strict version.

Complexity: O(n)

foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a

The strict version of foldl2AVL, which is useful for functions which are strict in their first argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy version gives (when used with strict functions) to O(log n).

Complexity: O(n)

Tree flattening utilities.

None of these functions preserve the tree shape (of course).

flatten :: AVL e -> AVL e

Flatten an AVL tree, preserving the ordering of the tree elements.

Complexity: O(n)

flatReverse :: AVL e -> AVL e

Similar to flatten, but the tree elements are reversed. This function has higher constant factor overhead than reverseAVL.

Complexity: O(n)

flatMap :: (a -> b) -> AVL a -> AVL b

Similar to mapAVL, but the resulting tree is flat. This function has higher constant factor overhead than mapAVL.

Complexity: O(n)

flatMap' :: (a -> b) -> AVL a -> AVL b

Same as flatMap, but the supplied function is applied strictly.

Complexity: O(n)

Sorting.

Nothing to do with AVL trees really. But using AVL trees do give an O(n.(log n)) sort algorithm for free, so here it is. These functions all consume the entire input list to construct a sorted AVL tree and then read the elements out as a list (lazily).

genSortAscending :: (e -> e -> COrdering e) -> [e] -> [e]

Uses the supplied combining comparison to sort list elements into ascending order. Multiple occurences of the same element are eliminated (they are combined in some way).

Complexity: O(n.(log n))

genSortDescending :: (e -> e -> COrdering e) -> [e] -> [e]

Uses the supplied combining comparison to sort list elements into descending order. Multiple occurences of the same element are eliminated (they are combined in some way).

Complexity: O(n.(log n))