Protocols With Associated Types

This is one of the few articles with a source. See the bottom of the page for more information.

Fear Mongering Preface

Be warned this is one of the hardest, most frustrating, and rare Swift features (at least when using UI). This is because it flips protocols on its head and forces you to think about types differently. Not to mention it often forces either the use of enums with associated values (another advanced topic) or type erasure (a topic I have yet to understand).

Enums with Associated Values

As you will find throughout this article, this a topic even I am still trying to grasp. So, I will do my best to explain everything as well as I can, but there will be some gaps in my knowledge. In fact, there is evidence that this is an unfinished feature, so my knowledge may become outdated soon.

Okay, for those I have not scared yet, the advantage for protocols with associated types or PATs is kind of like generics with classes (just kind of). I like to think of them as abstract classes (in Java) that are generic. If you remember from the discussion of protocols, our implementation of sets were limited to single types–we used integers specifically.

Associated Types

Let's fix this by making this parametric. Similar to generics, we need to create a name for our parametrizing type. To do this, we use the keyword associatedType followed by a type name, which can be constrained (more on this later). Let's call the type of our elements of our set Element: associatedType Element.

protocol Set {
    associatedtype Element
    /**
    Number of unique elements in the set
     */
    var length: Int { get }
    
    /**
    Unique elements in the set
     */
    var values: [Element] { get set }
    
    /**
    Adds `element` to the set.
     */
    mutating func add(_ element: Element)
    
    /**
    - returns:
     whether a set contains an element
     */
    func contains(_ element: Element) -> Bool
}

Then, when we want a type to conform or adopt our Set implementation, we can explicitly dictate the type with a typealias or be consistent with our typing.

struct IntegerSetExplicit: Set {
    typealias Element = Int
    
    var length: Int { values.count }
    
    var values = [Element]()
    
    mutating func add(_ element: Element) {
        if !contains(element) {
            values.append(element)
        }
    }
    
    func contains(_ element: Element) -> Bool {
        values.contains(element)
    }
    
    
}

struct IntegerSetImplicit: Set {
    
    var length: Int { values.count }
    
    var values = [Int]()
    
    mutating func add(_ element: Int) {
        if !contains(element) {
            values.append(element)
        }
    }
    
    func contains(_ element: Int) -> Bool {
        values.contains(element)
    }
}

Generic Constraint

This seems all well and dandy... Why is this so hard?

Let's try storing it in a variable...

var mySet: Set = ...

Oops, that doesn't compile... Well, actually that makes sense. If we think about this as a generic, we need to specify the type. Let's fix that:

protocol IntegerSet: Set where Element == Int {}
var myIntegerSet: IntegerSet = ...

The same error!

In fact, when working with PATs you will see this often:

"error: protocol '<SomeProtocol>' can only be used as a generic constraint because it has Self or associated type requirements"

In short, PATs are not types. You can only use them as constraints! This is a huge problem. Let's revisit the Swift standard library.

This, funnily enough, as Gallagher points out, is actually a list of all the ways you cannot use protocols with associated types.

Now you can get around some of this with Opaque typing, but that is a topic for another article, as I have yet to understand them!

So, what does this mean for us? We can't use PATs as types. We can only use them to show conformance. This means instead of using our protocol Set as a type we need a type that conforms to Set. If you have not reviewed generics and constraints, this may seem like a great sin and that Swift breaks all of your conceptions surrounding parametric polymorphism, but it doesn't. It's just annoying.

Let's say we want to write a function concatenate that takes in a bunch of sets and concatenates the result. If we were working with a normal protocol, we could do:

func concatenate(_ sets: [Set]) -> Set

But since, again, we can only use Set as a tool to show conformance. But, we want to keep this as widely applicable as possible. So, we use generics!

func concatenate<T: Set>(sets: [T]) -> T {
    assert(sets.count > 0)
    var base = sets[0]
    for set in sets[1..<sets.count] {
        for elt in set.values {
            base.add(elt)
        }
    }
    return base
}

This is basically the same, except for two differences. The less important is that we have given Set a new name. The more important is that all of our implementations of Set must be the exact same. This was not the case with normal protocols. This is where things get extra dicey.

If you want multiple implementations in the same list, there are two methods you can use. The first, which I highly suggest is enums with associated values–it's so OCaml and is very nice. The other is type erasure, which I sadly am not familiar with yet, so you will need to look into it yourself. But my vague understanding is that you use a wrapper type to abstract away the associated type and distill it into its barebones features to guarantee only what you need.

Conditional Functions

We can use constraints to add functionality! We can add constraints directly to the associated type if it is part of the invariant or conditionally to certain functions.

See constraints for more:

Constraints

contains seems like something we can implement broadly. Assuming we have access to equality, we can just iterate through the values and check!

extension Set {
    
    func contains(_ element: Element) -> Bool where Element: Equatable {
        for val in values {
            if val == element {
                return true
            }
        }
        return false
    }
    
}

Or, better yet, we can just Array's implementation of contains!

extension Set {
    
    func contains(_ element: Element) -> Bool where Element: Equatable {
        values.contains(element)
    }
    
}

For those of you that remember default implementations, this allows us to create conditional default implementations! This means that if we ever implement Set with a type that conforms to Equatable, we don't need to implement contains! Otherwise, we do.

Credits

Most of my understanding as well as my discussion originates from the following video. It is somewhat outdated, but it is a nice narrative of why this feature is the way it is and how to use it (kind of):