Set I

A Set is a data structure that represents a mathematical set. Unlike a list, it is very efficient (fast) to determine whether or not an item is in a set.

Sets do not remember the order in which elements are added.
Sets do not remember how many copies of an item are added. Adding an item that is already in a set does not change the set.

Qualified Imports

The import qualified statement prefixes all of the names in a module with a particular symbol. With the statement below, all of the Set functions should begin with “S.”.

import qualified Data.Set as S

Important Functions

You can look up all of the functions in the Data.Set package, but here are the most important ones:

empty: The empty list.
fromList: A good way to make a list for testing.
insert
member

There are plenty of other functions, including Set versions of map, filter, and fold.

One additional notable function is lookupGE, finds the smallest element greater than or equal to a given elemento. GE stands for greater than or equal to; there are also other variants.

lookupGE :: a -> S.Set a -> Maybe a

Quick Examples

nums :: S.Set Int
nums = S.fromList [10,20,30,40]

more_nums = S.insert 5 nums

original_nums = S.delete 5 more_nums

S.member 5 more_nums == True
S.notMember 17 more_nums == True

Exercises

(ps1) Given a list of ints, produce a set containing all of the partial sums beginning with the first number.
```
 ps1 :: [Int] -> S.Set Int
 c1 = (ps1 [10,40,90] == S.fromList [10,10+40,10+40+90])
```
(ps2) Given a list of ints, produce a set of all possible partial sums beginning with any one of the numbers, but still proceeding in order.
```
 ps2 :: [Int] -> S.Set Int
 c2 = (ps2 [10,40,90] == S.fromList [10, 10+40, 10+40+90, 40, 40+90, 90])
```

(countHits) Given a Set of String and a list of String, how many items in the list appear in the set.

 countHits :: S.Set String -> [String] -> Int

 ex3 :: S.Set String
 ex3 = S.fromList ["apple","blueberry","watermelon"]
 c3 = countHits ex3 ["pear","apple","apple","watermelon"] == 3

(aps) Given a list of integers xs and an integer n, return how far n is above the nearest partial sum. Assume that n is greater than at least one of the partial sums.

Example: xs = [10,40,90] and n = 55; the closest partial sum is 50, so return 55-50 = 5.
```
 aps :: [Int] -> Int -> Int
 c4 = aps [10,40,90] 55 == 5
```