swift - 实现 LazyCollectionProtocol

Question

所以我正在学习有关 LazySequenceProtocol 和 LazyCollectionProtocol 的教程。

首先，我尝试了来自 Apple's API reference 的示例代码并且能够实现符合 LazySequenceProtocol 的 LazyScanSequence，如下所示:

struct LazyScanIterator<Base : IteratorProtocol, ResultElement> : IteratorProtocol {
    mutating func next() -> ResultElement? {
        return nextElement.map { result in
            nextElement = base.next().map { nextPartialResult(result, $0) }
            return result
        }
    }
    private var nextElement: ResultElement? // The next result of next().
    private var base: Base                  // The underlying iterator.
    private let nextPartialResult: (ResultElement, Base.Element) -> ResultElement

    init(nextElement: ResultElement, base: Base, nextPartialResult: @escaping (ResultElement, Base.Element) -> ResultElement) {
        self.nextElement = nextElement
        self.base = base
        self.nextPartialResult = nextPartialResult
    }
}

struct LazyScanSequence<Base: Sequence, ResultElement> : LazySequenceProtocol // Chained operations on self are lazy, too
{
    func makeIterator() -> LazyScanIterator<Base.Iterator, ResultElement> {
        return LazyScanIterator(nextElement: initial, base: base.makeIterator(), nextPartialResult: nextPartialResult)
    }

    private let base: Base
    private let initial: ResultElement
    private let nextPartialResult: (ResultElement, Base.Iterator.Element) -> ResultElement

    init(initial: ResultElement, base: Base, nextPartialResult: @escaping (ResultElement, Base.Iterator.Element) -> ResultElement) {
        self.initial = initial
        self.base = base
        self.nextPartialResult = nextPartialResult
    }
}

成功了。当时我很开心。之后我想将它进一步扩展到 Collection，这样我就可以使用索引访问结果。

因为 LazyCollectionProtocol 是从 LazySequenceProtocol 和 Collection 继承的，所以我不得不添加更多的东西:

struct LazyScanCollection<Base: Collection, ResultElement> : LazyCollectionProtocol {
    func makeIterator() -> LazyScanIterator<Base.Iterator, ResultElement> {
        return LazyScanIterator(nextElement: initial, base: base.makeIterator(), nextPartialResult: nextPartialResult)
    }

    private let base: Base
    private let initial: ResultElement
    private let nextPartialResult: (ResultElement, Base.Iterator.Element) -> ResultElement

    init(initial: ResultElement, base: Base, nextPartialResult: @escaping (ResultElement, Base.Iterator.Element) -> ResultElement) {
        self.initial = initial
        self.base = base
        self.nextPartialResult = nextPartialResult
    }

    // ^--- #1 conform to Sequence

    typealias Index = Base.Index
    var startIndex: Index { return base.startIndex }
    var endIndex: Index { return base.endIndex }
    subscript (position: Index) -> Base.Iterator.Element {
        precondition(indices.contains(position), "out of boundsss")
        return base[position]
    }
    func index(after i: Index) -> Index {
        return base.index(after: i)
    }

    // ^--- #2 conform to IndexableBase
}

在添加 #2 部分之前，我有 2 个错误说 this does not conform to protocol Collection & IndexableBase。

添加#2后，即startIndex、endIndex、subscript、index(在:) 之后，有关IndexableBase 的错误之一消失了。但是我仍然有一个错误说这不符合Collection。

我认为#2 将满足Collection 的所有要求，但我想我错了。我不确定如何解决这个问题。

Answer 1

问题是您的 LazyScanCollection 的推断类型存在冲突的 Iterator.Element – 你的 makeIterator()方法说它是 LazyScanIterator<Base.Iterator, ResultElement>.Element 类型(又名 ResultElement )，但是您的 subscript说它的类型是 Base.Iterator.Element .

正确的类型是ResultElement ，这是通过迭代每个基本集合的元素获得的，应用 nextPartialResult函数以获得下一个元素。但是，您的下标实现不会这样做——相反，它会尝试直接 下标基。这不是您想要的，因为它不会返回“已扫描”元素，它只会返回扫描前的元素。

因此，您需要实现一个下标，该下标返回集合中给定索引的“已扫描”元素。实现这一点的一种方法是定义您自己的索引类型，以便将基数的下一个索引与当前的“累积”元素一起存储到下标。例如:

// An underlying index for a LazyScanCollection. Note that this will be invalidated
// if the base is mutated.
struct _LazyScanCollectionIndex<BaseIndex : Comparable, ResultElement> : Comparable {

    var nextBaseIndex: BaseIndex // the next index of base to access.
    var element: ResultElement // the currently 'accumulated' element.

    static func ==(lhs: _LazyScanCollectionIndex, rhs: _LazyScanCollectionIndex) -> Bool {
        return lhs.nextBaseIndex == rhs.nextBaseIndex
    }

    static func <(lhs: _LazyScanCollectionIndex, rhs: _LazyScanCollectionIndex) -> Bool {
        return lhs.nextBaseIndex < rhs.nextBaseIndex
    }
}

然后您可以构建一个 enum包装器以定义结束索引(这也可以通过将 nextBaseIndex 的 _LazyScanCollectionIndex 属性设为可选来实现，但我非常喜欢使用自定义枚举)。例如:

// A wrapper for the index of a LazyScanCollection
enum LazyScanCollectionIndex<BaseIndex : Comparable, ResultElement> : Comparable {

    // either an actual index, or the endIndex.
    case index(_LazyScanCollectionIndex<BaseIndex, ResultElement>)
    case endIndex

    static func ==(lhs: LazyScanCollectionIndex, rhs: LazyScanCollectionIndex) -> Bool {
        switch (lhs, rhs) {
        case (.endIndex, .endIndex):
            return true
        case let (.index(lhsIndex), .index(rhsIndex)):
            return lhsIndex == rhsIndex
        default:
            return false
        }
    }

    static func <(lhs: LazyScanCollectionIndex, rhs: LazyScanCollectionIndex) -> Bool {
        switch (lhs, rhs) {
        case (.index, .endIndex): // endIndex is greater than all indices.
            return true
        case let (.index(lhsIndex), .index(rhsIndex)):
            return lhsIndex < rhsIndex
        default:
            return false
        }
    }
}

然后你会想要调整你的 LazyScanCollection使用这个新索引类型的实现:

typealias Index = LazyScanCollectionIndex<Base.Index, ResultElement>

var startIndex: Index {
    return .index(_LazyScanCollectionIndex(nextBaseIndex: base.startIndex, element: initial))
}

var endIndex: Index {
    return .endIndex
}

func index(after i: Index) -> Index {

    guard case var .index(index) = i else {
        fatalError("Cannot advance past endIndex")
    }

    if index.nextBaseIndex < base.endIndex {
        // form the next partial result from the next index of the base and the
        // currently 'accumulated' element.
        index.element = nextPartialResult(index.element, base[index.nextBaseIndex])
        base.formIndex(after: &index.nextBaseIndex) // increment next index.
        return .index(index)
    } else {
        return .endIndex
    }
}

最后通过访问索引的 element 来实现你的下标属性:

subscript (position: Index) -> ResultElement {

    // ensure that the index is valid before subscripting.
    guard case let .index(index) = position, indices.contains(position) else {
        fatalError("Index \(position) out of bounds.")
    }

    return index.element
}

由于集合中元素的值取决于它之前所有元素的值，因此索引在线性时间内发生。如果您需要 O(1) 索引，您应该急切地执行 scan(_:_:)方法来生成数组而不是使用惰性集合。