llrbtree-0.1.1: Purely functional sets and heaps

Data.Set.Splay

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