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 Ints 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.