# 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 `Int`s 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 `Int`s 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 `Int`s.

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.