Implement `Array` & `ArraySlice` extension with a protocol instead

Question

I have the following Swift code:

extension Array {
  typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool

  func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
    return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
  }
}

extension ArraySlice {
  typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool
  
  func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
    return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
  }
}

extension CountableRange {
  typealias EqualTest = (Element, Element) -> Bool
  
  func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
    // Implementation omitted here.
    // For details see  "Background" at the end of the question.
  }
}

Rather than extend Array and ArraySlice with identical code, is there a protocol I can extend that will achieve the same result?

Essentially, I would like to extend any collection where the associated type Indices is a CountableRange.

Attempts at a generic implementation

I've tried to express this in many ways, but I've not found a way to make it compile.

Attempt 1

extension RandomAccessCollection {
  typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool

  func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
    // Error on next line…
    return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
  }
}

This attempt gives 2 errors:

Value of type 'Self.Indices' has no member 'groupSplitIndices'

Closure use of non-escaping parameter 'equal' may allow it to escape

(I think the second error is Swift getting confused.)

Attempt 2

extension RandomAccessCollection where Indices: CountableRange {
  // Implementation omitted.
}

Gives error:

Reference to generic type 'CountableRange' requires arguments in <...>

Attempt 3

extension RandomAccessCollection where Indices: CountableRange<Int> {
  // Implementation omitted.
}

Gives error:

Type 'Indices' constrained to non-protocol type 'CountableRange'

---

Background

Here's the extension on CountableRange implementing groupRanges(withEqualTest:) that is omitted above. The algorithm, what it does, and it's Big O cost is discussed in this question.

I have attempted to implement something similar as an extension of RandomAccessCollection, but didn't have much luck.

extension CountableRange {
  typealias EqualTest = (Element, Element) -> Bool
  
  func groupRanges(withEqualTest equal:EqualTest) -> [CountableRange] {
    let groupIndices = groupSplitIndices(withEqualTest: equal)
    return groupIndices.indices.dropLast().map {groupIndices[$0]..<groupIndices[$0+1]}
  }
  
  func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
    var allIndexes = [lowerBound]
    allIndexes.append(contentsOf: interiorGroupSplitIndices(withEqualTest: equal))
    allIndexes.append(upperBound)
    
    return allIndexes
  }
  
  func interiorGroupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
    var result = Array<Element>()
    var toDo = [self]
    
    while toDo.count > 0 {
      let range = toDo.removeLast()
      
      guard
        let firstElement = range.first,
        let lastElement = range.last,
        firstElement != lastElement,
        !equal(firstElement, lastElement) else {
          continue;
      }
      
      switch range.count {
      case 2:
        result.append(lastElement)
      default:
        let midIndex = index(firstElement, offsetBy: range.count/2)
        toDo.append(range.suffix(from: midIndex))
        toDo.append(range.prefix(through: midIndex))
      }
    }
    
    return result
  }
}

Answer 1

In order to call indices.groupSplitIndices() you need the constraint
Indices == CountableRange<Index> on the collection extension, and that requires Index to be Strideable:

extension RandomAccessCollection where Index: Strideable, Indices == CountableRange<Index> {

    typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool

    func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
        return indices.groupSplitIndices(withEqualTest: {
            equal(self[$0], self[$1])
        })
    }
}

extension CountableRange {
    typealias EqualTest = (Element, Element) -> Bool

    func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
        // Dummy implementation:
        return []
    }
}

and this actually compiles with Swift 4 (Xcode 9 beta or Xcode 8.3.3 with the Swift 4 toolchain).

There is one problem though: The Swift 3 compiler in Xcode 8.3.3 crashes when compiling the above code with the "Debug" configuration. That seems to be a compiler bug, because it compiles without problem in the "Release" configuration, and also with Xcode 9 or with Xcode 8.3.2 and the Swift 4 toolchain.

---

Here is a rough description how I figured out the above solution. Let's start with your "Attempt 3":

extension RandomAccessCollection where Indices: CountableRange<Int>

// error: type 'Indices' constrained to non-protocol type 'CountableRange<Int>

Indices can not be a subclass of or a type adopting CountableRange<Int>, which means that we need a same-typre requirement:

extension RandomAccessCollection where Indices == CountableRange<Int>

This results in

// error: cannot subscript a value of type 'Self' with an index of type 'Int'

at self[$0] and self[$1]. The subscript method of Collection takes a Self.Index parameter, so we change it to

extension RandomAccessCollection where Indices == CountableRange<Index>

// error: type 'Self.Index' does not conform to protocol '_Strideable'

So Index must be Strideable:

extension RandomAccessCollection where Index: Strideable, Indices == CountableRange<Index>

and that's it!