# Sets (Structs)

January 22, 2018

There are a lot of things to like about our setup in the past two posts. For instance, given two sets, we can find their intersection and union like this.

*
union(of: twoThreeFour, and: threeFourFive)
intersection(of: twoThreeFour, and: threeFourFive)
*

We can add and remove elements from a set like this.

*
add(7, to: twoThreeFour)
remove(4, from: twoThreeFour)
*

It's easy to forget that we've defined our set to be a function that takes an `Int` and returns a `Bool`.

*
typealias IntSet = (Int) -> Bool
*

In this post, I want to change our definition of `IntSet` a bit. Instead of it being a function, I want it to be a struct whose only property is a function with that signature.

Here's today's sample code and here's the Playground it comes from. Please note that, as the readme and license specify, this is based on code Copyrighted by Graham and is under the MIT license.

OK, here's the revised definition of `IntSet`.

*
struct IntSet {
let contains: (Int) -> Bool
}
*

We can use our struct to create a set representing all even numbers like this.

*
let evens = IntSet(contains: {x in
x % 2 == 0
})
*

Test that `evens` contains `4` but doesn't contain `3`. The first line below should be `true` and the second should be `false`.

*
evens.contains(4)
evens.contains(3)
*

One quick win of using a struct is we can now implement our free function which displays the element of our set between, say `0` and `10` as an implementation of `description`.

*
extension IntSet: CustomStringConvertible {
var description: String {
return [Int](0 ... 10)
.filter{x in contains(x)}
.description
}
}
*

Type `even` in the playground and you'll see `[0, 2, 4, 6, 8, 10]` in the right side of the playground.

I don't know if you're going to like this, but take a look at how we used `filter()`. Remember that if the last argument is a closure, we can write it as a trailing closure and move it outside of the argument list. We've done that when we typed

*
filter{x in contains(x)}
*

So here's the part you may not like. Instead of typing

*
let evens = IntSet(contains: {x in
x % 2 == 0
})
*

We can move the closure out of the argument list and instead type it like this.

*
let evens = IntSet{x in
x % 2 == 0
}
*

The part that feels funny is it doesn't look as if we're creating an instance of `IntSet` anymore. Some of my students prefer to type it like this - but I'll use the previous style for the rest of this article.

*
let evens = IntSet(){x in
x % 2 == 0
}
*

Let's get back to our struct.

I'd like to be able to create `IntSet`s from ranges of `Int`s as we did in the past and from a comma separated list of `Int`s. In other words, I'd love the following to work.

*
let twoThreeFour = IntSet(withRangeFrom: 2, to: 4)
let primes = IntSet(2, 3, 5, 7)
*

We need to add `init`s for these two styles. Unfortunately, this means that the automatically generated `init` for `contains` is no longer generated for us. So we need to fill out the `init`s for our `IntSet`.

*
struct IntSet {
let contains: (Int) -> Bool
init(contains: @escaping (Int) -> Bool) {
self.contains = contains
}
init(withRangeFrom lower: Int, to upper: Int) {
contains = {x in
(x >= lower) && (x <= upper)
}
}
init(_ elements: Int ...) {
contains = {x in
elements.contains(x)
}
}
}
*

Note that each of our `init`s specify the closure that we're storing in `contains`. Two other things to note is that (1) `contains` is our only property and (2) it is a `let`. It can't be modified.

We can create the empty set using the `init` that takes var args and not pass it any values and we can create the universal set by returning `true` for any x.

*
let emptySet = IntSet()
let universalSet = IntSet(contains: {(_) in return true})
*

What remains is to bring all of our free functions inside of the struct. I'll put them in an extension.

*
extension IntSet {
func union(_ otherSet: IntSet) -> IntSet {
return IntSet{ x in
(self.contains(x) || otherSet.contains(x))
}
}
func intersection(_ otherSet: IntSet) -> IntSet {
return IntSet{ x in
(self.contains(x) && otherSet.contains(x))
}
}
var complement: IntSet {
return IntSet{x in !self.contains(x)}
}
func minus(_ setToBeRemoved: IntSet) -> IntSet {
return self.intersection(setToBeRemoved.complement)
}
func symmetricDifference(with otherSet: IntSet) -> IntSet {
return self.union(otherSet).minus(self.intersection(otherSet))
}
func add(_ element: Int) -> IntSet {
return IntSet{x in
self.contains(x) || x == element
}
}
func remove(_ element: Int) -> IntSet {
return IntSet{ x in
self.contains(x) && x != element
}
}
}
*

To me, they feel more natural to use than they did as free functions - you may feel differently about that.

*
let threeFourFive = IntSet(3, 4, 5)
twoThreeFour.union(threeFourFive)
twoThreeFour.intersection(threeFourFive)
twoThreeFour.complement
twoThreeFour.minus(threeFourFive)
twoThreeFour.symmetricDifference(with: threeFourFive)
let addSeven = twoThreeFour.add(7)
let removeSeven = addSeven.remove(7)
let addSevenAgain = removeSeven.add(7)
*

So, as our second experiment with functions as objects, we've reimplemented sets as structs that contain a closure as their only property.