Module Data.Table.RBTree

Library with an implementation of tables as red-black trees:

A table is a finite mapping from keys to values. All the operations on tables are generic, i.e., one has to provide an explicit order predicate on elements. Each inner node in the red-black tree contains a key-value association.

Author: Johannes Koj, Michael Hanus, Bernd Brassel

Version: December 2018

Summary of exported operations:

empty :: Eq a => (a -> a -> Bool) -> RedBlackTree (a,b)  Deterministic 
Returns an empty table, i.e., an empty red-black tree.
isEmpty :: RedBlackTree (a,b) -> Bool  Deterministic 
tests whether a given table is empty
lookup :: a -> RedBlackTree (a,b) -> Maybe b  Deterministic 
Looks up an entry in a table.
update :: a -> b -> RedBlackTree (a,b) -> RedBlackTree (a,b)  Deterministic 
Inserts or updates an element in a table.
toList :: RedBlackTree (a,b) -> [(a,b)]  Deterministic 
Transforms the nodes of red-black tree into a list.
delete :: a -> RedBlackTree (a,b) -> RedBlackTree (a,b)  Deterministic 

Exported datatypes:

TableRBT

Type synonym: TableRBT a b = RedBlackTree (a,b)

Exported operations:

empty :: Eq a => (a -> a -> Bool) -> RedBlackTree (a,b)  Deterministic 

Returns an empty table, i.e., an empty red-black tree.

isEmpty :: RedBlackTree (a,b) -> Bool  Deterministic 

tests whether a given table is empty

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

lookup :: a -> RedBlackTree (a,b) -> Maybe b  Deterministic 

Looks up an entry in a table.

Example call:
(lookup k t)
Parameters:
  • k : a key under which a value is stored
  • t : a table (represented as a red-black tree)
Returns:
(Just v) if v is the value stored with key k, otherwise Nothing is returned.

update :: a -> b -> RedBlackTree (a,b) -> RedBlackTree (a,b)  Deterministic 

Inserts or updates an element in a table.

toList :: RedBlackTree (a,b) -> [(a,b)]  Deterministic 

Transforms the nodes of red-black tree into a list.

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

delete :: a -> RedBlackTree (a,b) -> RedBlackTree (a,b)  Deterministic