Exploring Functional Implementations of 'Set' Using Swift Enums

Swift gives us a Set type out of the box, but we can learn some neat lessons by exploring functional implementations of Set using Swift’s basic value types.

Most simply defined, a set is an unordered collection of unique objects. We can choose to represent sets in other ways (as ordered lists or as binary trees) - and this choice has dramatic implications for speed and efficiency of information retrieval - but here we’ll stick with the unordered list representation.

enum SimpleSet<T: Equatable> {
    case Empty
    indirect case Cons(T, SimpleSet<T>)
}

Swift’s enum type provides a concise and elegant way to represent the two possible states of a set (empty and not empty). We can construct a set easily now:

let set: SimpleSet<Int> = SimpleSet(3,
                                  SimpleSet(2,
                                    SimpleSet(1,
                                        SimpleSet)))

It’s nice to construct sets, but being able to operate on them would be great too. To that end we can go ahead and write a few operations to use on SimpleSet:

extension SimpleSet {
    func contains(element: T) -> Bool {
        switch self {
        case .Empty:
            return false
        case .Cons(let car, let cdr):
            return element == car ? true : cdr.contains(element)
        }
    }
}

contains matches against self, returning false if self is empty, true if the element passed in is equal to the first element of self, and recursively calls itself if neither of those conditions are met.

extension SimpleSet {
    func prepend(element: T) -> SimpleSet<T> {
        return contains(element) ? self : .Cons(element, self)
    }
}

prepend takes an element and, if not already contained in the set, constructs a new set and returns it.

extension SimpleSet {
    func unionWithSet(set: SimpleSet<T>) -> SimpleSet {
        switch set {
        case .Empty:
            return self
        case .Cons(let car, let cdr):
            return prepend(car).unionWithSet(cdr)
        }
    }
}

unionWithSet matches against the set that is passed in, returning self if the set is empty and otherwise recursively calling unionWithSet on a new SimpleSet that consists of the current set with the first element of the passed-in set prepended to it (if that element is not already contained in the current set).

extension SimpleSet {
    func intersectionWithSet(set: SimpleSet) -> SimpleSet {
        switch (self, set) {
        case (.Cons(_, _), .Cons(let car, let cdr)):
            return contains(car) ? .Cons(car, intersectionWithSet(cdr)) : intersectionWithSet(cdr)
        default:
            return .Empty
        }
    }
}

intersectionWithSet works in a similar fashion. However, instead of matching against self, it matches against a tuple consisting of both self and the passed-in set. If either of the sets are empty, then the intersection is the empty set. If both are non-empty, then intersectionWithSet checks if the first element of the passed-in set is contained in the current set; if so, it returns a new set consisting of that element prepended onto a set that is the return value of the tail (the list of elements in the passed-in set minus the first element) passed into intersectionWithSet; if not, it simply returns intersectionWithSet called on the tail of the passed-in set.

####Conclusion With this small handful of functions, we have a more-or-less complete Set implementation. We could enhance the lookup speed of individual elements within our set by choosing to represent it in an ordered fashion or as a tree, but this stripped-down implementation gives us a data structure with a plenty of utility and shows how functional concepts like pattern matching and recursion can be used to implement basic set operations in a concise and readable fashion.