Hiding default implementations in refinements

[dabrahams]

I was working with this design

trait Collection {
  type Element
  type Position: Regular
  fun start() -> Position
  fun end() -> Position
  fun position(after i: sink Position) -> Position
  subscript(_ i: Position): Element { let }
  
  /// Requires: `q` does not precede `p`
  fun distance(from p: sink Position, to q: Position) -> Int {
    var n = 0
    while p != q { p = position(after: p); n += 1 }
    return n
  }

   /// Requires `n >= 0`
  fun position(_ p: sink Position, offset_by n: sink Int) -> Position {
    while n > 0 { p = position(after: p); n -= 1 }
    return p
  }
}

Now when you get to RandomAccessCollection, you really want to require distance and position to be reimplemented in O(1). The topic raised is whether we need a feature to hide the defaults.

An alternative I thought of was :

trait RandomAccessCollection: Collection {
  /// O(1) please
  fun offset_from_start(_ p: Position) -> Int
  /// O(1) please
  fun nthPosition(_ n: Int) -> Position
}

extension RandomAccessCollection {
  fun distance(from p: sink Position, to q: Position) -> Int {
    offset_from_start(q) - offset_from_start(p)
  }

  fun position(_ p: sink Position, offset_by n: Int) -> Position {
    nthPosition(offset_from_start(p) + n)
  }
}

I don't love that because

1. It's redundant
2. I can think of scenarios where measuring q - p might sometimes be faster than (q - start) - (p - start), e.g. p and q are in the same segment of a Deque. That's minor but real. If we classified something with pseudolinear traversal like a B-tree as random access it might get real-er.

[kyouko-taiga]

What if we just repeat the requirement in RandomAccessCollection, with a default implementation that uses the conformance to Collection?

trait P {
  // - Complexity: O(n)
  fun f(n: Int) -> Int
}

trait Q: P {
  // - Note: Please provide O(1) implementation is `Self::P.f(n:)` isn't.
  fun f(n: Int) -> Int { Self::P.f(self: self, n: n) } 
}

Since there is no way in general to check that a particular implementation has O(x) complexity, we can only rely on the user to satisfy the semantic requirement that's documented in Q.

This setup makes it possible to write the following, assuming A's conformance to P already provides a constant time implementation for f(n:)

conformance A: P { fun f(n: Int) -> Int { n.copy() } }
conformance A: Q {}

There may be some complications with the way we can create the most refined witness table but I don't have any obvious showstopper on the top of my head.