Why the Swift compiler is not able to infer generic type when opaque type is returned for conforming to the `Sequence` protocol

Question

I have a Swift package with implementation of a LinkedList class. I want to make my LinkedList conforming to the Sequence protocol. For that makeIterator returns LinkedListIterator instance which is hidden behind opaque IteratorProtocol type like follows:

extension LinkedList: Sequence {
    public func makeIterator() -> some IteratorProtocol {
        LinkedListIterator(head: head)
    }
}

With the opaque type as above, I have a compilation error when I want to use Sequence features such as map:

func test_list_has_expected_elements() {
    let list = LinkedList(2, 4, 2, 3)
    XCTAssertEqual(list.map{ $0 }, [2, 4, 2, 3]) //Cannot convert value of type 'Int' to expected element type 'Array<(some IteratorProtocol).Element>.ArrayLiteralElement' (aka '(some IteratorProtocol).Element')
}

After changing the Sequence conformance from opaque type to LinkedListIterator<T> it compiles without errors, however it imposes LinkedListIterator implementation to be public what is not desired.

extension LinkedList: Sequence {
    public func makeIterator() -> LinkedListIterator<T> {
        LinkedListIterator(head: head)
    }
}

How to change the implementation to use the opaque type and have the Sequence API available?

Here is full implementation of my LinkedList:

public class LinkedList<T> {
    
    var head: Node<T>?
    
    init(_ elements : T...) {
        if let first = elements.first {
            var last = Node(data: first)
            head = last
            elements.dropFirst(1).forEach { element in
                let next = Node(data: element)
                last.next = next
                last = next
            }
        }
    }
    
    public func append(data: T) {
        let newNode = Node(data: data)
        if let last {
            last.next = newNode
        } else {
            head = newNode
        }
    }
    
    public var count: UInt {
        var runner = head
        var count: UInt = 0
        while let node = runner {
            count += 1
            runner = node.next
        }
        return count
    }
    
    private var last: Node<T>? {
        if var runner = head {
            while let next = runner.next {
                runner = next
            }
            return runner
        }
        return nil
    }
}


@available(macOS 10.15, iOS 13.0, watchOS 6.0, tvOS 13.0, *)
extension LinkedList: Sequence {
    /*
    public func makeIterator() -> LinkedListIterator<T> {
        LinkedListIterator(head: head)
    }
    */
    
    public func makeIterator() -> some IteratorProtocol {
        LinkedListIterator(head: head)
    }
}

public struct LinkedListIterator<T>: IteratorProtocol {
    
    private var currentNode: Node<T>?
    
    init(head: Node<T>? = nil) {
        self.currentNode = head
    }
    
    public mutating func next() -> T? {
        if let node = currentNode {
            currentNode = node.next
            return node.data
        } else {
            return nil
        }
    }
}

Swift details: swift-driver version: 1.62.15 Apple Swift version 5.7.1 (swiftlang-5.7.1.135.3 clang-1400.0.29.51)

Answer 1

You just need to make a small tweak and it'll work:

extension LinkedList: Sequence {
    public func makeIterator() -> some IteratorProtocol<T> {
        LinkedListIterator(head: head)
    }
}

Without specializing IteratorProtocol on T the compiler will think its Element is Any (i.e. some opaque iterator type with any element type).

Answer 2

You will get error even with:

XCTAssertEqual(list.map{ $0 }, list.map{ $0 })

It's problem of opaque types, that you know nothing about it's associatedtype type. So better to return exact type if you can. Opaque types just needed when you have monstrous generics in the result.