Purely functional top-down splay sets.

- D.D. Sleator and R.E. Rarjan, "Self-Adjusting Binary Search Tree", Journal of the Association for Computing Machinery, Vol 32, No 3, July 1985, pp 652-686. http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

- data Splay a
- empty :: Splay a
- singleton :: a -> Splay a
- insert :: Ord a => a -> Splay a -> Splay a
- fromList :: Ord a => [a] -> Splay a
- toList :: Splay a -> [a]
- member :: Ord a => a -> Splay a -> (Bool, Splay a)
- delete :: Ord a => a -> Splay a -> Splay a
- deleteMin :: Splay a -> (a, Splay a)
- deleteMax :: Splay a -> (a, Splay a)
- null :: Splay a -> Bool
- union :: Ord a => Splay a -> Splay a -> Splay a
- intersection :: Ord a => Splay a -> Splay a -> Splay a
- difference :: Ord a => Splay a -> Splay a -> Splay a
- split :: Ord a => a -> Splay a -> (Splay a, Bool, Splay a)
- minimum :: Splay a -> (a, Splay a)
- maximum :: Splay a -> (a, Splay a)
- valid :: Ord a => Splay a -> Bool
- (===) :: Eq a => Splay a -> Splay a -> Bool
- showSet :: Show a => Splay a -> String
- printSet :: Show a => Splay a -> IO ()

# Data structures

# Creating sets

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

Insertion.

`>>>`

True`insert 5 (fromList [5,3]) == fromList [3,5]`

`>>>`

True`insert 7 (fromList [5,3]) == fromList [3,5,7]`

`>>>`

True`insert 5 empty == singleton 5`

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

Creating a set from a list.

`>>>`

True`empty == fromList []`

`>>>`

True`singleton 'a' == fromList ['a']`

`>>>`

True`fromList [5,3,5] == fromList [5,3]`

# Converting a list

toList :: Splay a -> [a]Source

Creating a list from a set.

`>>>`

[3,5]`toList (fromList [5,3])`

`>>>`

[]`toList empty`

# Membership

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

Checking if this element is a member of a set?

`>>>`

True`fst $ member 5 (fromList [5,3])`

`>>>`

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

# Deleting

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

Deleting this element from a set.

`>>>`

True`delete 5 (fromList [5,3]) == singleton 3`

`>>>`

True`delete 7 (fromList [5,3]) == fromList [3,5]`

`>>>`

True`delete 5 empty == empty`

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

Deleting the minimum element.

`>>>`

True`snd (deleteMin (fromList [5,3,7])) == fromList [5,7]`

`>>>`

*** Exception: deleteMin`deleteMin empty`

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

Deleting the maximum

`>>>`

True`snd (deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")])) == fromList [(3,"b"), (5,"a")]`

`>>>`

*** Exception: deleteMax`deleteMax empty`

# Checking

See if the splay set is empty.

`>>>`

True`Data.Set.Splay.null empty`

`>>>`

False`Data.Set.Splay.null (singleton 1)`

# Set operations

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

Creating a union set from two sets.

`>>>`

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

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

Creating a intersection set from sets.

`>>>`

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

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

Creating a difference set from sets.

`>>>`

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

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

`>>>`

1`fst $ minimum (fromList [3,5,1])`

`>>>`

*** Exception: minimum`minimum empty`

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

Finding the maximum element.

`>>>`

5`fst $ maximum (fromList [3,5,1])`

`>>>`

*** Exception: maximum`maximum empty`