Transitioning a lazy sequence to a collection

I've tried making Sequence extended methods to simulate C++'s std::unique_copy, and I'm trying to make a lazy variant.

/// An iterator that vends only the elements of the wrapped iterator that don't preceed an element with an equivalent value.
public struct LazyFilterAdjacentValuesIterator<Base: IteratorProtocol> {
    var base: Base
    let areEquivalent: (Base.Element, Base.Element) -> Bool
    var last: Base.Element? = nil

    /// Creates an iterator wrapping the given one, along with the equivalence relation for testing.
    init(_ base: Base, by areEquivalent: @escaping (Base.Element, Base.Element) -> Bool) {
        self.base = base
        self.areEquivalent = areEquivalent
    }
}

extension LazyFilterAdjacentValuesIterator: IteratorProtocol {
    public mutating func next() -> Base.Element? {
        while let element = base.next() {
            if let lastElement = last, areEquivalent(lastElement, element) {
                continue
            }
            last = element
            return element
        }
        return nil
    }
}

/// A sequence that vends only the elements of the wrapped sequence that don't preceed an element with an equivalent value.
public struct LazyFilterAdjacentValuesSequence<Base: Sequence> {
    let base: Base
    let areEquivalent: (Base.Element, Base.Element) -> Bool
}

extension LazyFilterAdjacentValuesSequence: Sequence {
    public func makeIterator() -> LazyFilterAdjacentValuesIterator<Base.Iterator> {
        return LazyFilterAdjacentValuesIterator(base.makeIterator(), by: areEquivalent)
    }
    public var underestimatedCount: Int { return base.underestimatedCount.signum() }
}

extension LazyFilterAdjacentValuesSequence: LazySequenceProtocol {}

extension LazySequenceProtocol {
    /// Returns the elements of `self` that are not equivalent to their predecessor, using the given predicate as the equivalence test.
    public func filterAdjacentValues(by areEquivalent: @escaping (Element, Element) -> Bool) -> LazyFilterAdjacentValuesSequence<Elements> {
        return LazyFilterAdjacentValuesSequence(base: elements, areEquivalent: areEquivalent)
    }
}

extension LazySequenceProtocol where Element: Equatable {
    /// Returns the elements of `self` that are not equal to their predecessor.
    public func filterAdjacentValues() -> LazyFilterAdjacentValuesSequence<Elements> {
        return filterAdjacentValues(by: ==)
    }
}

I noticed that LazySequenceProtocol.map and filter have a special mode to have those sequences act like collections when the wrapped sequence is also a collection. I tried that:

extension LazyFilterAdjacentValuesSequence: Collection where Base: Collection {
    public var startIndex: Base.Index { return base.startIndex }
    public var endIndex: Base.Index { return base.endIndex }
    public subscript(position: Base.Index) -> Base.Element { return base[position] }
    public func index(after i: Base.Index) -> Base.Index {
        return base[base.index(after: i)...].firstIndex(where: { !areEquivalent(base[i], $0) }) ?? endIndex
    }
}

I did have a type-alias of "LazyFilterAdjacentValuesCollection<T: Collection> = LazyFilterAdjacentValuesSequence<T>," with an extension on LazyFilterAdjacentValuesCollection unconditionally conforming to Collection but it didn't make a difference on the errors I got:

  • Type 'AnySequence<Base.Element>' does not conform to protocol 'Collection'
  • Type 'LazyFilterAdjacentValuesSequence<Base>' does not conform to protocol 'Collection'

What is the Standard Library doing right that I'm doing wrong? (I'm using Xcode 10.1, with Swift 4.2.)

The default subsequence is AnySequence<Base.Element>. Maybe try defining it as Slice<Base.Element>.

You might want to look into the standard library's implementation then.

Well, I tried following an example at the Swift GitHub:

public struct LazyFilterAdjacentValuesSequence<Base: Sequence> {
    let base: Base
    let areEquivalent: (Base.Element, Base.Element) -> Bool
}

extension LazyFilterAdjacentValuesSequence: Sequence {
    //public typealias SubSequence = AnySequence<Base.Element>
    public func makeIterator() -> LazyFilterAdjacentValuesIterator<Base.Iterator> {
        return LazyFilterAdjacentValuesIterator(base.makeIterator(), by: areEquivalent)
    }
    public var underestimatedCount: Int { return base.underestimatedCount.signum() }
}

extension LazyFilterAdjacentValuesSequence: LazySequenceProtocol {}

public typealias LazyFilterAdjacentValuesCollection<T: Collection> = LazyFilterAdjacentValuesSequence<T>

extension LazyFilterAdjacentValuesCollection: Collection {
    //public typealias Index = Base.Index
    //public typealias SubSequence = LazyFilterAdjacentValuesCollection<Base.SubSequence>
    public var startIndex: Base.Index { return base.startIndex }
    public var endIndex: Base.Index { return base.endIndex }
    public subscript(position: Base.Index) -> Base.Element { return base[position] }
    public subscript(bounds: Range<Base.Index>) -> LazyFilterAdjacentValuesCollection<Base.SubSequence> {
        return LazyFilterAdjacentValuesCollection(base: base[bounds], areEquivalent: areEquivalent)
    }
    public func index(after i: Base.Index) -> Base.Index {
        return base[base.index(after: i)...].firstIndex(where: { !areEquivalent(base[i], $0) }) ?? endIndex
    }
}

There are two errors on the line defining the extension for Collection:

  • Type 'AnySequence<Base.Element>' does not conform to protocol 'Collection'
  • Type 'LazyFilterAdjacentValuesSequence<Base>' does not conform to protocol 'Collection'

I'm using Xcode 10.1, which I think comes with Swift 4.2.1. The current Swift system at GitHub is set for a Swift 5.0 beta, I think. I think a big blocker is that SubSequence is locked to AnySequence in the Sequence extension and I have to completely redo it for the Collection extension, and Swift won't allow the override. This isn't a problem in Swift 5 because S5 rips out Sequence.SubSequence, so its Collection.SubSequence has no conflicts.

  1. Can anyone check that this code works for Swift 5?
  2. Is there a workaround for Swift 4.2? Or do I have to wait for S5?
Terms of Service

Privacy Policy

Cookie Policy