Question: Implementing LazyCollectionProtocol

Question

Implementing LazyCollectionProtocol

Answers 1
Added at 2016-12-30 11:12
Tags
Question

So I was following tutorials about LazySequenceProtocol and LazyCollectionProtocol.

First, I tried sample codes from Apple's API reference and was able to implement LazyScanSequence that conforms to LazySequenceProtocol like below:

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
    }
}

It worked. I was happy. And after that I wanted to extend it further to Collection, so that I could access the result by using indices.

Since LazyCollectionProtocol is inherited from both LazySequenceProtocol and Collection I had to add more stuffs:

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
}

Before adding #2 part, I had 2 errors saying this does not conform to protocol Collection & IndexableBase.

After adding #2, that is startIndex, endIndex, subscript, and index(after:), one of the errors about IndexableBase disappeared. But I still have an error saying that this does not conform to Collection.

I thought #2 will fulfill all requirements for Collection, but I guess I was wrong. I'm not sure how to fix this problem.

Answers to

Implementing LazyCollectionProtocol

nr: #1 dodano: 2016-12-30 15:12

The problem is that you have conflicting inferred types for your LazyScanCollection's Iterator.Element – your makeIterator() method says that it's of type LazyScanIterator<Base.Iterator, ResultElement>.Element (aka. ResultElement), however your subscript says that it's of type Base.Iterator.Element.

The correct type is ResultElement, which is obtained by iterating through each of the base collection's elements, applying the nextPartialResult function in order to get the next element. However, your subscript implementation doesn't do this – instead it attempts to subscript the base directly. This isn't what you want, as it wouldn't return the 'scanned' element, it would just return the element prior to scanning.

Therefore you need to implement a subscript which returns a 'scanned' element for a given index of the collection. One way of implementing this would be to define your own index type in order to store the next index of the base to subscript, along with the currently 'accumulated' element. For example:

// 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
    }
}

You could then build an enum wrapper in order to define an end index (this could also be implemented by making the nextBaseIndex property of the _LazyScanCollectionIndex an optional, but I quite like using a custom enum). For example:

// 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
        }
    }
}

You would then want to adapt your LazyScanCollection's implementation to use this new index type:

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
    }
}

And then finally implement your subscript by simply accessing the index's element property:

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
}

As the value of an element in the collection depends on the values of all elements prior to it, indexing takes place in linear time. If you require O(1) indexing, you should eagerly perform the scan(_:_:) method in order to generate an array rather than using a lazy collection.

Source Show
◀ Wstecz