Set Operations in Haskell

In this topic we are going to concentrate on following things

1. Introduction to implementation of sets and Set Operations
2. Functions related to construction of sets
3. Show tree functions on sets
4. Splitting functions of sets
5. Min / Max functions on sets
6. Conversion functions on sets
7. Query functions on sets
8. Combine functions on sets

Introduction to implementation of sets and set Operations

1. The implementation of Set is based on size balanced binary trees like AVL trees.
2. To implement set operations we must know corresponding algorithm Ex: for Union, Hedge union Algorithm
3. Must know the advanced concepts of Haskell like Tip, Bin, foldr, monoid, Foldable and many more concepts.
4. All set operations already implemented. Available in “Data.Set” Container of Haskell.

Functions related to construction of sets

Syntax: fromList :: [a] -> set a
Description: Creates a set from a list of elements.

Syntax: singleton :: a -> Set a
Description: Creates a singleton set with element ‘a’.

Syntax: insert :: a -> Set a -> Set a
Description: Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.

Syntax: delete :: a -> Set a -> Set a
Description: Delete an element from a set.

Exercise-1: Construct a set S = {a, b, d, c, e} and delete ‘b’ from that set and add ‘f’ to set.

Exercise-2: Construct singleton set S = {0.123}. Add 9.8 to that set and delete 0.98 from that set.

Showing Tree functions on sets

Syntax: showTree:: Set a -> String
Description: Shows the compressed tree that implements set.

Syntax: showTreeWith:: Bool -> Bool -> Set a -> String
Description: shows the tree that implements the set. If hang is true, a hanging tree is shown. If wide is true, an extra wide version of tree is shown.

Exercise-1: From set S = {a, b, e, d, c} generate a string from which we can draw corresponding balanced tree.
Note: Use putStrLn Function

Splitting functions on sets

Syntax: partition ::(a -> Bool) -> Set a -> (Set a, Set a)
Description: Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate.

Syntax: split :: a -> Set a -> (Set a, Set a)
Description: The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x.

Syntax: splitMember :: a -> Set a -> (Set a, Bool, Set a)
Description: Performs a split but also returns whether the pivot element was found in the original set.

Exercise-1: Divide the set S = {f, h, k, l, o, a, p, r, t} into two sets S1 and S2. Set S1 with elements less than ‘m’ and set S2 with elements greater than ‘m’.

Min / Max functions on sets

Syntax: findMin :: Set a -> a
Description: Returns the minimal element of a set.

Syntax: findMax :: Set a -> a
Description: Returns the maximal element of a set.

Syntax: deleteMin :: Set a -> Set a
Description: Delete the minimal element from set.

Syntax: deleteMax :: Set a -> Set a
Description: Delete the maximal element from set.

Syntax: deleteFindMin :: Set a -> (a, Set a)
Description: Finds and deletes the minimal element of set.

Syntax: deleteFindMax :: Set a -> (a, Set a)
Description: Finds and deletes the minimal element of set.

Exercise-1: Express the deleteFindMin in terms of findMin and deleteMin and give one suitable example.

Exercise-2: Express the deleteFindMax in terms of findMax and deleteMax and give one suitable example.

Conversion functions on sets

Syntax: elems :: Set a -> [a]
Description: Convert the set to a list of elements.

Syntax: toList :: Set a -> [a]
Description: Convert the set to a list of elements.

Query functions on sets

Syntax: null :: Set a -> Bool
Description: checks for given set is null or not.

Syntax: size :: Set a -> Int
Description: Returns the number of elements in the set.

Syntax: member :: a -> Set a -> Bool
Description: Checks for the given element belongs to set or not.

Syntax: notMember :: a -> Set a -> Bool
Description: Checks given element doesn’t belongs to set or not

Syntax: isSubsetOf :: Set a -> Set a -> Bool
Description: Checks for given set is subset or not.

Syntax: isProperSubsetOf :: Set a -> Set a -> Bool
Description: Checks for given set is subset or not.

Exercise-1: Write instruction to check {0.32, 0.21, 0.10} is proper subset of {0.10, 0.32, 0.21}?

Combine functions on sets

Syntax: union :: Set a -> Set a -> Set a
Description: Performs union operation on given two sets.

Syntax: unions :: [Set a] -> Set a
Description: Performs union operation on set of sets.

Syntax: intersection :: Set a -> Set a -> Set a
Description: performs intersection operation on given two sets.

Syntax: difference :: Set a -> Set a -> Set
Description: Finds the difference of given two sets.

Exercise-1: let S = {1, 3, 4, 6, 7} and T = {2, 5, 8, 9, 0, 4, 6}.
Write instruction to find n (S U T).

Exercise-2: let P = {1, 3, 4, 6, 7}, Q = {2, 5, 8, 9, 0, 4, 6} and R
= {2, 5, 6, 1, 3}. Write instruction to find n (P U Q U R).