# Sets

January 16, 2018

« Previous

Functional Programmers look at the world differently than Object-Oriented Programmers. It's more than that functions are first class members, we use functions in different ways than many of us are used to.

Graham Lee is going to deliver a talk at dotSwift in a couple of weeks based on a series of playgrounds he's published on GitHub called OOP in FP in Swift.

In this post I look at Graham's first example in which he asks that you imagine you are going to implement a set. It's a simple set that only tells you whether or not it contains an element.

Here's my 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.

You might think that your main choice is whether to use a class or a struct.

A functional programmer says, why not use a function.

In particular, a functional programmer might implement a set as a function that takes an argument of the type the set contains and returns a `Bool` that is `true` if the set contains the element and `false` if it doesn't.

In code, here's the definition of our `SimpleSet`.

*
typealias SimpleSet<Element> = (Element) -> Bool
*

In our case, let's simplify the example to only consider sets that contain elements of type `Int`.

We can either define an `IntSet` like this

*
typealias IntSet = SimpleSet<Int>
*

or we can eliminate the need for `SimpleSet` and define `IntSet` like this

*
typealias IntSet = (Int) -> Bool
*

With this in hand, the empty set is an `IntSet` that returns `false` for any value you give it.

*
let emptySet: IntSet = {(_) in return false}
*

Now, you can ask if the `emptySet` contains, say, `5` like this.

*
emptySet(5)
*

The result is `false`.

Similarly, you can define the set that contains every element, the `universalSet`, using a function that always returns `true`.

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

The `universalSet` contains every element, so you can test for `5`.

*
universalSet(5)
*

The result is `true`.

To create a set that contains a range of `Int`s we return a function that returns `true` exactly when `x` is an `Int` between (and including) the lower and upper bounds.

*
func rangeSet(from lower: Int,
to upper: Int) -> IntSet {
return { x in
(x >= lower) && (x <= upper)
}
}
*

So we can create an instance of a `rangeSet` like this.

*
let threeFourFive = rangeSet(from: 3, to: 5)
*

`threeFourFive` includes `3` and `4` but not `2`. So, `threeFourFive(2)` is `false` and both `threeFourFive(3)` and `threeFourFive(4)` are `true`.

Hang on a second. I said, "create an instance of a `rangeSet`".

`rangeSet` is a function that returns a specific type of `IntSet`.

Kind of cool.

OK, create a second `rangeSet`.

*
let twoThreeFour = rangeSet(from: 2, to: 4)
*

We have two sets. Let's calculate their union and intersection. Here's how we define functions to take the union and intersection of sets.

*
func union(of firstSet: @escaping IntSet,
and secondSet: @escaping IntSet) -> IntSet {
return { x in
(firstSet(x) || secondSet(x))
}
}
func intersection(of firstSet: @escaping IntSet,
and secondSet: @escaping IntSet) -> IntSet {
return { x in
(firstSet(x) && secondSet(x))
}
}
*

You can verify that the intersection and union give the results you expect:

*
let twoThroughFive = union(of: twoThreeFour, and: threeFourFive)
let threeAndFour = intersection(of: twoThreeFour, and: threeFourFive)
*

If you're new to this way of thinking, it's pretty unexpected that we can define a set as a function and get union and intersection working as well. Of course, we can take this example further but that's enough for now.

You'll see this same approach in the objc.io book on Functional Swift. They begin with an example that takes disc shaped regions and combines them to build pretty complicated shapes. Everything starts with the definition of a `Region` as

*
typealias Region = (Position) -> Bool
*

A `Region` is just a function that returns `true` if the `Region` contains the `Position` and `false` if it doesn't.

This is a technique that pops up quite a bit. In future posts we'll consider different aspects of FP and programming in Swift more generally.