## Exploring Functional Implementations of 'Set' Using Swift Enums

Swift gives us a `Set`

type out of the box, but we can learn some neat lessons by exploring functional implementations of `Set`

using Swift’s basic value types.

Most simply defined, a set is an unordered collection of unique objects. We can choose to represent sets in other ways (as ordered lists or as binary trees) - and this choice has dramatic implications for speed and efficiency of information retrieval - but here we’ll stick with the unordered list representation.

```
enum SimpleSet<T: Equatable> {
case Empty
indirect case Cons(T, SimpleSet<T>)
}
```

Swift’s `enum`

type provides a concise and elegant way to represent the two possible states of a set (empty and not empty). We can construct a set easily now:

```
let set: SimpleSet<Int> = SimpleSet(3,
SimpleSet(2,
SimpleSet(1,
SimpleSet)))
```

It’s nice to construct sets, but being able to operate on them would be great too. To that end we can go ahead and write a few operations to use on `SimpleSet`

:

```
extension SimpleSet {
func contains(element: T) -> Bool {
switch self {
case .Empty:
return false
case .Cons(let car, let cdr):
return element == car ? true : cdr.contains(element)
}
}
}
```

`contains`

matches against `self`

, returning `false`

if `self`

is empty, `true`

if the element passed in is equal to the first element of `self`

, and recursively calls itself if neither of those conditions are met.

```
extension SimpleSet {
func prepend(element: T) -> SimpleSet<T> {
return contains(element) ? self : .Cons(element, self)
}
}
```

`prepend`

takes an element and, if not already contained in the set, constructs a new set and returns it.

```
extension SimpleSet {
func unionWithSet(set: SimpleSet<T>) -> SimpleSet {
switch set {
case .Empty:
return self
case .Cons(let car, let cdr):
return prepend(car).unionWithSet(cdr)
}
}
}
```

`unionWithSet`

matches against the set that is passed in, returning `self`

if the set is empty and otherwise recursively calling `unionWithSet`

on a new `SimpleSet`

that consists of the current set with the first element of the passed-in set prepended to it (if that element is not already contained in the current set).

```
extension SimpleSet {
func intersectionWithSet(set: SimpleSet) -> SimpleSet {
switch (self, set) {
case (.Cons(_, _), .Cons(let car, let cdr)):
return contains(car) ? .Cons(car, intersectionWithSet(cdr)) : intersectionWithSet(cdr)
default:
return .Empty
}
}
}
```

`intersectionWithSet`

works in a similar fashion. However, instead of matching against `self`

, it matches against a `tuple`

consisting of both `self`

and the passed-in set. If either of the sets are empty, then the intersection is the empty set. If both are non-empty, then `intersectionWithSet`

checks if the first element of the passed-in set is contained in the current set; if so, it returns a new set consisting of that element prepended onto a set that is the return value of the tail (the list of elements in the passed-in set minus the first element) passed into `intersectionWithSet`

; if not, it simply returns `intersectionWithSet`

called on the tail of the passed-in set.

####Conclusion
With this small handful of functions, we have a more-or-less complete `Set`

implementation. We could enhance the lookup speed of individual elements within our set by choosing to represent it in an ordered fashion or as a tree, but this stripped-down implementation gives us a data structure with a plenty of utility and shows how functional concepts like pattern matching and recursion can be used to implement basic set operations in a concise and readable fashion.