# CSCE 314: Programming Languages

# Assignment 4

## Objective

In this assignment you'll create your own type, and write functions that operate on that type.

## Instructions

- This assignment asks you to implement a set of Haskell functions. Each of those functions can be defined with just a few lines of code. If your implementations start to get much longer, it may be a sign that there are less complicated solutions that you may be missing. Nevertheless, you may need to implement several functions (maybe as many as five) that you can put together to give a solution.

## Sets, Set products, Partitions, and Bell Numbers

The following problems are to implement mathematical sets and some of their
operations using Haskell lists. A set is an *unordered*
collection of elements (objects) without duplicates, whereas a list is
an *ordered* collection of elements in which multiplicity of
the same element is allowed.

We do not define a new type for sets, but instead define `Set`

as a *type synonym* for lists as follows:

type Set a = [a]

Note: if your type definitions have the extra class constraint: (Ord a) => ... for any of the solutions given below, that is acceptable too.

Even though the types `Set a`

and `[a]`

are
the same to the Haskell compiler, to the programmer they communicate
that values of the former are sets while the values of the latter
are arbitrary lists.

### Set constructor

Write a recursive function that constructs a set.

mkSet :: Eq a => [a] -> Set a

Constructing a set from a list simply means removing all duplicate
values. (Hint: Use `isElement`

in the definition.)

### Subset

Write a recursive function `subset`

, such that
`subset a b`

returns `True`

if
`a`

is a subset of `b`

and `False`

otherwise.
(Hint: you should write a function that can determine if some value is a member of a set.)

subset :: Eq a => Set a -> Set a -> Bool

### Set equality

Using `subset`

you have already defined,
write a function `setEqual`

that returns
`True`

if the two sets contain exactly the same elements,
and `False`

otherwise.

setEqual :: Eq a => Set a -> Set a -> Bool

### Set product

The product of two sets **A** and **B** is the set
consisting of all pairs draw from either set, where the pairs are ordered having
elements **(a _{i}, b_{j})**. The first element is from

**A**and the second from

**B**.

setProd :: (Eq t, Eq t1) => Set t -> Set t1 -> Set (t, t1)

Here's an example:

> setProd [1,2,3] ['a', 'b'] [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

### Set partition

The partition of a set **S** is defined as a set of nonempty,
pairwise disjoint subsets of **S** whose union is **S**.
For example, the set ```
{red,
green,
blue}
```

can be
partitioned in 5 ways:

```
{ {red}, {green}, {blue} }
```

{ {red}, {green, blue} }

{ {green}, {red, blue} }

{ {blue}, {red, green} }

{ {red, green, blue} }.

Write a Haskell function to compute the partition of any set provided as input. (The colors are just to help you see the pattern; your code isn't expected to produce the colored output.)

partitionSet :: Eq t => Set t -> Set( Set (Set t))

### Computing Bell numbers

The Bell number **B _{n}** is the number of partitions of a set of size

**n**. Use your previous answer to write a function that computes the Bell number for any non-negative

**n**. (Note that

**B**.)

_{0}= B_{1}= 1bellNum :: Int -> Int

Here's an example:

> bellNum 5 52

### Check your answers

Here is the testing bundle. (Updated 20-Feb-2017).
Testing these cases is a bit more involved than earlier examples and some
requiring that more than one file be added to the GHCi workspace via the
`:a`

operation. Please have a look at the `Readme`

file
in the bundle for further details. If you need additional clarification, please post to piazza.