Hello everyone,
Some of you may recognize a similar protocol from another of my posts:
protocol Stack {
associatedtype Element
func push(element: Element) -> S
func pop() -> (Self, Element?)
}
Say I want to adopt this protocol with a simple linked list implementation:
class List<Element>: Stack {
var element: Element
var next: List?
// I really wish for SE-0018 to be implemented one day ...
init(element: Element, next: List? = nil) {
self.element = element
self.next = next
}
func push(element: Element) -> List {
return List(element: element, next: self)
}
func pop() -> (List, Element?) {
return next == nil ? (self, nil) : (next!, element)
}
}
This solution won't work, because List is not final. I guess the reason is that a subclass would not fulfill the self-requirement imposed by the protocol Stack for the methods push(element:) and pop(). One could use Self, as suggested by the compiler. While this can solve the problem for the push(element:) method (additionally requiring a way to reliably initializing a Self instance, e.g. by marking List's initializer required), it does not work for pop() because its return type is a tuple (by the way I think (Self, Element?) should work in theory, as tuples seems to be covariant).
By navigating a little on the forum, I found a solution by declaring an additional associated type in Stack with a same-type requirement on Self, and use it in the return types of push(element:) and pop():
protocol Stack {
associatedtype Element
associatedtype S where S == Self
func push(element: Element) -> S
func pop() -> (S, Element?)
}
// List's code is unchanged
class SortedList<Element>: List<Element> where Element: Comparable {
override func push(element: Element) -> SortedList {
// some completely irrelevant implementation ...
}
}
This looks awfully hacky, but appears to work like a charm. SortedList.push(element:) is properly overridden and returns a SortedList, while List.pop() is inherited and returns a List, as expected (I know there would be far far better approaches to implement this that would not even have to rely on class inheritance, but my point isn't really about linked lists). Unfortunately, I don't understand why ...
I thought that protocol conformance was checked at every level of a class hierarchy. By this logic, it would make perfect sense that the first solution (using Self as a return type) does not work. But then this second approach shouldn't either, because SortedList inherits from a method List.pop() that does not fulfill the same-type requirement defined on Stack's associated type. Worse, S does not even represent the same type in SortedList's two methods, which leaves me wondering how type inference was able to solve it.
Could anyone enlighten me on the magic that leaves the type solver happy with this contrived example?