Purely functional splay sets.
- 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)
- deleteMin :: Splay a -> (a, Splay a)
- null :: Splay a -> Bool
- union :: Ord a => Splay a -> Splay a -> Splay a
- partition :: Ord a => a -> Splay a -> (Splay a, Bool, Splay a)
- minimum :: Splay a -> (a, Splay a)
- valid :: Ord 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.
>>>
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. O(N)
>>>
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
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
Checking
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
Helper functions
partition :: 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.