swiftgenericsiteratoropaque-types

Generic type conforms to Sequence with help of opaque type: some IteratorProtocol


protocol TreeNode: AnyObject {
    associatedtype T
    var value: T { get set }
    var children: [Self] { get }
    init(_ value: T)
}

protocol Tree: Sequence {
    associatedtype Node: TreeNode
    var root: Node? { get set }
}

extension Tree {
    typealias T = Node.T
    
    func makeIterator() -> some IteratorProtocol {
        BFSIterator(startFrom: root)
    }
}

This compiles and looks very promising.
But then all of a sudden in Unit Tests line let sum = tree.reduce(0, +) cause compilation error:

Cannot convert value of type '(Int) -> Int' to expected argument type '(Int, (some IteratorProtocol).Element) throws -> Int'

Why compiler can't figure out that (some IteratorProtocol).Element is indeed Int? And how to help it?

Note, that if I make "an old way" (without opaque types): func makeIterator() -> BFSIterator { everything compiles and works perfectly.

Update:

struct BFSIterator<Node: TreeNode>: IteratorProtocol {
    private var queue: Queue<Node> = []
    
    init(startFrom root: Node?) {
        root.map { queue.push($0) }
    }
    
    mutating func next() -> Node.T? {
        guard let current = queue.pop() else { return nil }
        queue.push(contentsOf: current.children)
        return current.value
    }
}

Solution

  • This happens because there's no way in current Swift (5.2) to specify the associated type for an opaque return value. Thus, some IteratorProtocol is not enough for the compiler to figure out what kind of values should the next() method return.

    This limitation of the language forces you to explicitly declare the iterator type if you want to actually use the sequence.