Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

List related utilities for AVL trees.

- asListL :: AVL e -> [e]
- toListL :: AVL e -> [e] -> [e]
- asListR :: AVL e -> [e]
- toListR :: AVL e -> [e] -> [e]
- asTreeLenL :: Int -> [e] -> AVL e
- asTreeL :: [e] -> AVL e
- asTreeLenR :: Int -> [e] -> AVL e
- asTreeR :: [e] -> AVL e
- genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e
- genPushList :: (e -> e -> COrdering e) -> AVL e -> [e] -> AVL e
- reverseAVL :: AVL e -> AVL e
- mapAVL :: (a -> b) -> AVL a -> AVL b
- mapAVL' :: (a -> b) -> AVL a -> AVL b
- traverseAVL :: Applicative f => (a -> f b) -> AVL a -> f (AVL b)
- replicateAVL :: Int -> e -> AVL e
- filterViaList :: (e -> Bool) -> AVL e -> AVL e
- mapMaybeViaList :: (a -> Maybe b) -> AVL a -> AVL b
- partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
- foldrAVL :: (e -> a -> a) -> a -> AVL e -> a
- foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a
- foldr1AVL :: (e -> e -> e) -> AVL e -> e
- foldr1AVL' :: (e -> e -> e) -> AVL e -> e
- foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a
- foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a
- foldlAVL :: (a -> e -> a) -> a -> AVL e -> a
- foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a
- foldl1AVL :: (e -> e -> e) -> AVL e -> e
- foldl1AVL' :: (e -> e -> e) -> AVL e -> e
- foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a
- foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a
- flatten :: AVL e -> AVL e
- flatReverse :: AVL e -> AVL e
- flatMap :: (a -> b) -> AVL a -> AVL b
- flatMap' :: (a -> b) -> AVL a -> AVL b
- genSortAscending :: (e -> e -> COrdering e) -> [e] -> [e]
- genSortDescending :: (e -> e -> COrdering e) -> [e] -> [e]

# 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).

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]Source

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)

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]Source

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 eSource

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)

As `asTreeLenL`

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

Complexity: O(n)

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

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)

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 eSource

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 eSource

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 eSource

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 bSource

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 bSource

Similar to `mapAVL`

, but the supplied function is applied strictly.

Complexity: O(n)

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

replicateAVL :: Int -> e -> AVL eSource

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 eSource

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 bSource

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)Source

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 -> aSource

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 -> aSource

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 -> eSource

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 -> eSource

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 -> aSource

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 -> aSource

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 -> aSource

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 -> aSource

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 -> eSource

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 -> eSource

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 -> aSource

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 -> aSource

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 eSource

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

Complexity: O(n)

flatReverse :: AVL e -> AVL eSource

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 bSource

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]Source

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]Source

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))