Sets (Free Functions)

January 18, 2018

In the first article on Sets, we looked at how we might implement a set of integers named IntSet as a function.

The idea is to play around with a different way of looking at something that we think we're familiar with and see what happens.

We easily created sets that were a range of Ints and saw how to form unions and intersections.

I thought that was pretty good. We were able to ask a set if it contained a particular element by evaluate the set with the element as the parameter.

We're going to take this a bit further today. 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.

Here's our definition of IntSet, a constructor for a set that contains a range of Ints named rangeSet, and a set named twoThreeFour.


typealias IntSet = (Int) -> Bool

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

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

I'd actually like a way of displaying the contents of the sets we create. Here's a simple approach that displays all of the sets contents within some bounds. Here I'm defaulting to between 0 and 10 but you can specify different bounds.


func contents(of set: IntSet,
                from lowerBound: Int = 0,
                to upperBound: Int = 10) -> String {
    return [Int](lowerBound...upperBound)
          .filter{x in set(x)}.description
}

Now we can display


contents(of: twoThreeFour)

The console shows this as [2,3,4].

Remember, twothreefour is just a function Int -> Bool.

We already have union and intersection, it might be nice to have complement. As you'd expect, the complement just returns true if the element is not in the original set.


func complement(of set: @escaping IntSet) -> IntSet {
    return {x in !set(x)}
}

The complement of twothreefour is an infinite set consisting of all of the numbers less than or equal to 1 and those greater than or equal to 5.


contents(of: complement(of: twoThreeFour))

The console shows this as [0, 1, 5, 6, 7, 8, 9, 10].

Yes, I'd prefer that this rendered as {..., 1, 5, ...} or {..., 0, 1, 5, 6, ...}, but I didn't see a quick way of doing this in contents(). (If you have a thought, please share it in the discussion.)

With union, intersection, and complement, we can easily add difference and symmetric difference.


func difference(of baseSet: @escaping IntSet, 
	                       minus setToBeRemoved: @escaping IntSet) -> IntSet {
    return intersection(of: baseSet, 
                        and: complement(of: setToBeRemoved))
}

func symmetricDifference(of setOne: @escaping IntSet, 
                         and setTwo: @escaping IntSet) -> IntSet {
    let unionSet = union(of: setOne, 
                         and: setTwo)
    let intersectionSet = intersection(of: setOne, 
                                       and: setTwo)
    return difference(of: unionSet, 
                      minus: intersectionSet)
}

Take these for a test drive.


contents(of: difference(of: twoThroughFive, 
	                    minus: threeAndFour))
contents(of: symmetricDifference(of: twoThreeFour, 
                                 and: threeFourFive))

These both yield [2, 5].

One of you complained that we only have sets of consecutive Ints.

We can now obviously use these different set operations to get sets with gaps in them. Let's also make it easier to create a new IntSet consisting of specified elements.


func setFrom(elements: Int...) -> IntSet {
    return {x in
        elements.contains(x)
    }
}

We can use this to create a set of prime numbers like this.


let primes = setFrom(elements: 2, 3, 5, 7)

A set is still a function. The intersection of two sets is also a function. And so on.

For kicks lets find the union of primes and twoThreeFour.


union(of: primes, and: twoThreeFour)

Show the contents of this and see [2, 3, 4, 5, 7]. Note we don't get [2, 3, 5, 7, 2, 3, 4] or [2, 2, 3, 3, 4, 5, 7].

I know that that's obvious, but it means that we get the uniqueness feature of a set for free.

We probably want to be able to add and remove objects. We can implement them like this.


func add(_ element: Int, 
	                to set: @escaping IntSet) -> IntSet {
    return {x in
        set(x) || x == element
    }
}

func remove(_ element: Int, 
            from set: @escaping IntSet) -> IntSet {
    return { x in
        set(x) && x != element
    }
}

So let's take twothreefour and add 7, then remove 7, and then add it again.


let addSeven = add(7, to: twoThreeFour)
let removeSeven = remove(7, from: addSeven)
let addSevenAgain = add(7, to: removeSeven)

The results are [2, 3, 4, 7], [2, 3, 4], and [2, 3, 4, 7], respectively.

We're checking that if we remove something we've added then it isn't there anymore and then if we add it back that it didn't stay removed.

An IntSet is just a function (Int) -> Bool but we've been able to do a lot of set-like things with it.

This is pretty ugly.

There are a lot of free functions floating around.

Next time, we'll modify our example to make it feel nicer to use.