A different kind of Set

Here’s a different way of implementing a Set in Swift:

struct Set<Element: Equatable> {
    var contains: (Element) -> Bool
}

You can initialize an instance like this:

let set = Set<Int> { $0 == 42 }

And test for membership like so:

set.contains(42) // returns true
set.contains(43) // returns false

And while it lacks some very useful features we expect from a typical Set, because it can’t iterate over its members, our Set also has some tricks up its sleeve:

let allEvenNumbers = Set<Int> { $0 % 2 == 0 }

allEvenNumbers.contains(2) // returns true
allEvenNumbers.contains(224243532) // returns true
allEvenNumbers.contains(224243533) // returns false

That’s how easy it is to define a set containing all even numbers in existence, a set of infinite size.

How about mutation? That can be done by updating contains with an additional condition:

extension Set {
    mutating func insert(_ element: Element) {
        let _contains = contains
        contains = { $0 == element || _contains($0) }
    }
    
    mutating func remove(_ element: Element) {
        let _contains = contains
        contains = { $0 != element && _contains($0) }
    }
}

It’s funny to me that adding uses the logical OR operator while removing is done using the AND operator. It probably has something to do with algebra. I wouldn’t be able to explain why.

I do know that it allows us to create a set with a size of infinity minus one:

var manyNumbers = Set<Int> { $0 % 2 == 0 }
manyNumbers.remove(42)

manyNumbers.contains(40) // returns true
manyNumbers.contains(42) // returns false
manyNumbers.contains(44) // returns true

Epilogue

As I’m writing this, I find myself thinking about it some more. That’s always a risk because if I can’t find the words to put these thoughts to paper, this blog post will never see the light of day.

I was thinking about how this Set would fit in Swift’s standard library. Quite badly, it seems. It represents a collection, but it can’t conform to the Collection protocol. It can’t even conform to Sequence, since that requires sequential access to its elements. In the standard library, all collections must be iterable. Does that mean that if something is not iterable, it’s not a collection? Or is our Set here an example of a different kind of collection that the standard library does not accommodate for?