PAKCS
Exported names: Imported modules:

Module Data.Set.RBTree

Library with an implementation of sets as red-black trees.

All the operations on sets are generic, i.e., one has to provide an explicit order predicate (<) (less-than) on elements.

Author: Johannes Koj, Michael Hanus, Bernd Brassel

Version: December 2018

Summary of exported operations:

empty :: Eq a => (a -> a -> Bool) -> RedBlackTree a   
Returns an empty set, i.e., an empty red-black tree augmented with an order predicate.
null :: RedBlackTree a -> Bool   
Test for an empty set.
member :: a -> RedBlackTree a -> Bool   
Returns true if an element is contained in a (red-black tree) set.
insert :: a -> RedBlackTree a -> RedBlackTree a   
Inserts an element into a set if it is not already there.
insertMulti :: Eq a => a -> RedBlackTree a -> RedBlackTree a   
Inserts an element into a multiset.
delete :: a -> RedBlackTree a -> RedBlackTree a   
delete an element from a set.
toList :: RedBlackTree a -> [a]   
Transforms a (red-black tree) set into an ordered list of its elements.
union :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a   
Computes the union of two (red-black tree) sets.
intersection :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a   
Computes the intersection of two (red-black tree) sets.
sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]   
Generic sort based on insertion into red-black trees.

Exported datatypes:

SetRBT

Type synonym: SetRBT a = RedBlackTree a

Exported operations:

empty :: Eq a => (a -> a -> Bool) -> RedBlackTree a   

Returns an empty set, i.e., an empty red-black tree augmented with an order predicate.

Further infos:
  • solution complete, i.e., able to compute all solutions

null :: RedBlackTree a -> Bool   

Test for an empty set.

Further infos:
  • solution complete, i.e., able to compute all solutions

member :: a -> RedBlackTree a -> Bool   

Returns true if an element is contained in a (red-black tree) set.

Example call:
(member e s)
Parameters:
  • e : an element to be checked for containment
  • s : a set (represented as a red-black tree)
Returns:
True if e is contained in s

insert :: a -> RedBlackTree a -> RedBlackTree a   

Inserts an element into a set if it is not already there.

insertMulti :: Eq a => a -> RedBlackTree a -> RedBlackTree a   

Inserts an element into a multiset. Thus, the same element can have several occurrences in the multiset.

delete :: a -> RedBlackTree a -> RedBlackTree a   

delete an element from a set. Deletes only a single element from a multi set

toList :: RedBlackTree a -> [a]   

Transforms a (red-black tree) set into an ordered list of its elements.

Further infos:
  • solution complete, i.e., able to compute all solutions

union :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a   

Computes the union of two (red-black tree) sets. This is done by inserting all elements of the first set into the second set.

intersection :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a   

Computes the intersection of two (red-black tree) sets. This is done by inserting all elements of the first set contained in the second set into a new set, which order is taken from the first set.

sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]   

Generic sort based on insertion into red-black trees. The first argument is the order for the elements.