Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
Conversion utilities.
Modules.
Description

Many of the functions defined by this package make use of generalised comparison functions which return a variant of the Prelude Ordering data type: COrdering. These are refered to as "combining comparisons". (This is because they combine "equal" values in some manner defined by the user.)

The idea is that using this simple mechanism you can define many practical and useful variations of tree (or general set) operations from a few generic primitives, something that would not be so easy using plain Ordering comparisons (overloaded or otherwise).

Functions which involve searching a tree really only require a single argument function which takes the current tree element value as argument and returns an Ordering or COrdering to direct the next stage of the search down the left or right sub-trees (or stop at the current element). For documentation purposes, these functions are called "selectors" throughout this library. Typically a selector will be obtained by partially applying the appropriate combining comparison with the value or key being searched for. For example..

 mySelector :: Int -> Ordering               Tree elements are Ints
 or..
 mySelector :: (key,val) -> COrdering val    Tree elements are (key,val) pairs
 

Please read the notes in the Data.Tree.AVL.Types module documentation too.

Synopsis
set2AVL :: Set a -> AVL a
avl2Set :: AVL a -> Set a
map2AVL :: Map key val -> AVL (key, val)
avl2Map :: AVL (key, val) -> Map key val
module Data.Tree.AVL.Types
module Data.Tree.AVL.Size
module Data.Tree.AVL.Read
module Data.Tree.AVL.Write
module Data.Tree.AVL.Push
module Data.Tree.AVL.Delete
module Data.Tree.AVL.List
module Data.Tree.AVL.Join
module Data.Tree.AVL.Split
module Data.Tree.AVL.Set
module Data.Tree.AVL.Zipper
Conversion utilities.
set2AVL :: Set a -> AVL a

Convert a Set (from the base package Data.Set module) to a sorted AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Set :: AVL a -> Set a

Convert a sorted AVL tree to a Set (from the base package Data.Set module). Elements and element ordering are preserved.

Complexity: O(n)

map2AVL :: Map key val -> AVL (key, val)

Convert a Map (from the base package Data.Map module) to a sorted (by key) AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Map :: AVL (key, val) -> Map key val

Convert a sorted (by key) AVL tree to a Map (from the base package Data.Map module). Elements and element ordering are preserved.

Complexity: O(n)

Modules.
module Data.Tree.AVL.Types
module Data.Tree.AVL.Size
module Data.Tree.AVL.Read
module Data.Tree.AVL.Write
module Data.Tree.AVL.Push
module Data.Tree.AVL.Delete
module Data.Tree.AVL.List
module Data.Tree.AVL.Join
module Data.Tree.AVL.Split
module Data.Tree.AVL.Set
module Data.Tree.AVL.Zipper
Produced by Haddock version 0.7