llrbtree-0.1.1: Purely functional sets and heaps

Data.Set.Splay

Contents

Description

Purely functional top-down splay sets.

Synopsis

Data structures

data Splay a Source

Constructors

Leaf 
Node (Splay a) a (Splay a) 

Instances

Eq a => Eq (Splay a) 
Show a => Show (Splay a) 

Creating sets

empty :: Splay aSource

Empty set.

singleton :: a -> Splay aSource

Singleton set.

insert :: Ord a => a -> Splay a -> Splay aSource

Insertion.

>>> insert 5 (fromList [5,3]) == fromList [3,5]
True
>>> insert 7 (fromList [5,3]) == fromList [3,5,7]
True
>>> insert 5 empty            == singleton 5
True

fromList :: Ord a => [a] -> Splay aSource

Creating a set from a list.

>>> empty == fromList []
True
>>> singleton 'a' == fromList ['a']
True
>>> fromList [5,3,5] == fromList [5,3]
True

Converting a list

toList :: Splay a -> [a]Source

Creating a list from a set.

>>> toList (fromList [5,3])
[3,5]
>>> toList empty
[]

Membership

member :: Ord a => a -> Splay a -> (Bool, Splay a)Source

Checking if this element is a member of a set?

>>> fst $ member 5 (fromList [5,3])
True
>>> fst $ member 1 (fromList [5,3])
False

Deleting

delete :: Ord a => a -> Splay a -> Splay aSource

Deleting this element from a set.

>>> delete 5 (fromList [5,3]) == singleton 3
True
>>> delete 7 (fromList [5,3]) == fromList [3,5]
True
>>> delete 5 empty            == empty
True

deleteMin :: Splay a -> (a, Splay a)Source

Deleting the minimum element.

>>> snd (deleteMin (fromList [5,3,7])) == fromList [5,7]
True
>>> deleteMin empty
*** Exception: deleteMin

deleteMax :: Splay a -> (a, Splay a)Source

Deleting the maximum

>>> snd (deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")])) == fromList [(3,"b"), (5,"a")]
True
>>> deleteMax empty
*** Exception: deleteMax

Checking

null :: Splay a -> BoolSource

See if the splay set is empty.

>>> Data.Set.Splay.null empty
True
>>> Data.Set.Splay.null (singleton 1)
False

Set operations

union :: Ord a => Splay a -> Splay a -> Splay aSource

Creating a union set from two sets.

>>> union (fromList [5,3]) (fromList [5,7]) == fromList [3,5,7]
True

intersection :: Ord a => Splay a -> Splay a -> Splay aSource

Creating a intersection set from sets.

>>> intersection (fromList [5,3]) (fromList [5,7]) == singleton 5
True

difference :: Ord a => Splay a -> Splay a -> Splay aSource

Creating a difference set from sets.

>>> difference (fromList [5,3]) (fromList [5,7]) == singleton 3
True

Helper functions

split :: Ord a => a -> Splay a -> (Splay a, Bool, Splay a)Source

Splitting smaller and bigger with splay. Since this is a set implementation, members must be unique.

minimum :: Splay a -> (a, Splay a)Source

Finding the minimum element.

>>> fst $ minimum (fromList [3,5,1])
1
>>> minimum empty
*** Exception: minimum

maximum :: Splay a -> (a, Splay a)Source

Finding the maximum element.

>>> fst $ maximum (fromList [3,5,1])
5
>>> maximum empty
*** Exception: maximum

valid :: Ord a => Splay a -> BoolSource

Checking validity of a set.

(===) :: Eq a => Splay a -> Splay a -> BoolSource

Checking if two splay sets are exactly the same shape.