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).