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 IntSets from ranges of Ints as we did in the past and from a comma separated list of Ints. 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 inits 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 inits 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 inits 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.