Generics, Protocols and Associated Types

My desire to revisit priority queues was driven by "Classic Computer Science Problems in Swift: Essential techniques for practicing programmers". This book is a fun read. It's almost like reliving my sophomore year in college. It makes me feel young again ;)

I haven't written much Swift code that defined generics and protocols with associated types. These concepts aren't hard to understand, but as a long-time Python developer, I find Swift's boilerplate distracting and sometimes hard to read. When I get it wrong, the compiler error messages usually leave me scratching my head.

I'm also a long-time C++ developer, so yeah, I know it could be worse.

"Classic Computer Science Problems" seems to understand the psychological quirks of software developers and how to use them as a motivational tool.

The author presents a few code examples that use standard Swift protocols, and he explains why they are needed. Next he presents a generic depth-first search function. Then he explains that the breadth-first search algorithm is identical to depth-first search, differing only in the type of data structure used for the "frontier" - the container of states ready to be explored. And then (sprinkle the itching powder) he presents a full page of BFS code that differs by only one line from the earlier presentation of DFS.

The resulting urge to refactor is overwhelming.

In Python this type of refactoring is dead simple: just add a parameter via which to pass the "frontier" data structure.

(I've recently begun using optional type annotations and mypy. Even with the added type annotations, the Python code is simple.)

Maybe it's just because I'm unfamiliar with these aspects of Swift, but for me it was much harder to do this refactoring in Swift.

The frontier needs to implement an interface - conform to a protocol - that the generic search function understands. Since the protocol describes operations on a container, it has an associated type: the type of item that the container can hold.

// "P" for Protocol?  Forgive my un-Swifty style.
protocol PPushPop {
    associatedtype Element

    func push(_ newValue: Element)
    func pop() -> Element?
    var isEmpty: Bool { get }
}

The search function needs to declare that the frontier's contained objects have a type that is composed, in part, of the search functions's templated type. This is the bit that gave me trouble.

I started by defining a generic class as a namespace for all of the type declarations...

class Search<StateType> where StateType: Hashable, StateType: Comparable {
    typealias SNode = Node<StateType>    
    typealias GoalTestFn = (StateType) -> Bool
    typealias SuccessorsFn = (StateType) -> [StateType]
    ...

... and for the generic search function that uses them.

    static func search<F: PPushPop> (
        initial: StateType, frontier: F,
        isGoal: GoalTestFn, successors: SuccessorsFn) -> SNode?

The compiler needed to know that F would contain SNodes. Because I hadn't provided this info, it spewed several error messages:

Cannot convert value of type 'Node<StateType>?' to expected argument type 'Node<_>?'
Value of type 'F.Element' has no member 'state'
Cannot convert return expression of type 'F.Element' to return type 'Node<StateType>?'

To describe the required relationship between F.Element and SNode, I needed a trailing "where" clause. Thank goodness for "Advanced Swift", by Eidhof et al. It made it easy to understand how to compose the clause.

    static func search<F: PPushPop> (
        initial: StateType, frontier: F,
        isGoal: GoalTestFn, successors: SuccessorsFn) -> SNode?
        where F.Element == SNode