Struggling to express dependent givens under modularity

Language Design
1

I’am struggling to express the following idea:

  1. You have a type class representing collections
  2. You define a type representing slices of a collection
  3. You state that slices are collections having the same associated types of their bases
  4. You state that slices of a base conforming to some trait also conform to that trait

Note that requirement (3) implies that you can’t just take an arbitrary witness of a slice’s base being a collection to define that slice’s conformance to collection. In other words, the problem is a bit more tricky than the classic “lists of showable things are showable”. The complication is due to the fact that the value of a slice is composed of parts depending on the base being a collection in one specific way.

I managed to get the following foundations to work, satisfy requirements (1), (2), and (3):

trait Collection:
  type Self; type Position; type Element
  extension (self: Self) def apply(p: Position): Element

object Collection:
  final class Slice[P, E](
      C: Collection { type Position = P; type Element = E },
      private val base: C.Self
  ):
    def apply(p: P): E = base(p)

given [P, E] => Collection.Slice[P, E] is Collection:
  type Position = P; type Element = E
  extension (self: Self) def apply(p: P): E = self(p)
Full version 
import language.experimental.modularity
import annotation.tailrec

trait Collection:
  me =>

  type Self
  type Position
  type Element

  extension (self: Self)
    def start: Position
    def end: Position
    def positionAfter(p: Position): Position
    def apply(p: Position): Element

    def slice(low: Position, high: Position): Collection.Slice[Position, Element] =
      Collection.Slice(this, self, low, high)

    def sameElements[C](other: C)(
        using w: C is Collection { type Element = me.Element }
    ): Boolean =
      @tailrec def loop(i: Position, j: w.Position): Boolean =
        if i == self.end then
          j == other.end
        else if (j != self.end) && (self(i) == other(j)) then
          loop(self.positionAfter(i), other.positionAfter(j))
        else
          false
      loop(self.start, other.start)

object Collection:

  final class Slice[P, E](
      C: Collection { type Position = P; type Element = E },
      private val base: C.Self, val start: P, val end: P
  ):
    final def positionAfter(p: P): P = base.positionAfter(p)
    final def apply(p: P): E = base(p)

given [P, E] => Collection.Slice[P, E] is Collection:
  type Position = P
  type Element = E

  extension (self: Self)
    def start: P = self.start
    def end: P = self.end
    def positionAfter(p: P): P = self.positionAfter(p)
    def apply(p: P): E = self(p)

def demo[T: Collection](xs: T): Boolean =
  xs.sameElements(xs.slice(xs.start, xs.end))

As an aside, one thing I dislike about this approach is that I’m tracking the associated types of Slice’s conformance to Collection in Slice’s signature, as generic parameters. I’m doing that because I want slices to have the same elements and positions as their base collection.

More importantly, I got stuck when I tried to implement requirement (4). For example, assume I have the following type class:

trait MutableCollection:
  extension (self: Self)
    def update(p: Position, e: Element): Unit

Then, I’d like to say that Slice is a MutableCollection iff its base is as well.

I tried to define Slice in terms of a conformance argument.

final class Slice[T](using val T: T is Collection)(base: T)

Sadly, I wasn’t able to provide a conformance of this alternative representation of Slice to Collection. More details about my attempt below.

Note that using tracked parameter didn’t help.

Full version 
object Collection:

  final class Slice[T](using val T: T is Collection)(
      base: T, val start: T.Position, val end: T.Position
  ):
    final def positionAfter(p: T.Position): T.Position = base.positionAfter(p)
    final def apply(p: T.Position): T.Element = base(p)

given [T](using w: T is Collection) => (Collection.Slice[T] { val T: w.type }) is Collection:
  type Position = w.Position
  type Element = w.Element

  extension (self: Self)
    def start: w.Position = self.start
    def end: w.Position = self.end
    def positionAfter(p: w.Position): w.Position = self.positionAfter(p)
    def apply(p: w.Position): w.Element = self(p)

def demo[T: Collection](xs: T): Boolean =
  // The following triggers an error:
  //   No given instance of type Collection.Slice[evidence$1.Self] is
  //   Collection{type Element = evidence$1.Element} was found for parameter w of method sameElements in trait Collection
  xs.sameElements(xs.slice(xs.start, xs.end))

In case anyone’s wondering, I’m trying to express the following Swift setup in Scala:

Original motivation 
protocol Collection {
  associatedtype Position: Equatable
  associatedtype Element: Equatable

  var start: Position { get }
  var end: Position { get }
  func position(after p: Position) -> Position
  subscript(p: Position) -> Element { get }
}

extension Collection {
  subscript(low: Position, high: Position) -> Slice<Self> {
    Slice(base: self, start: low, end: high)
  }
  func sameElements<C: Collection>(other: C) -> Bool {
    func loop(i: Self.Position, j: C.Position) -> Bool {
      if i == self.end {
        return j == other.end
      } else if (j != self.end) && (self[i] == other[j]) {
        return loop(i: self.position(after: i), j: other.position(after: j))
      } else {
        return false
      }
    }
    return loop(i: self.start, j: other.start)
  }
}

protocol BidirectionalCollection: Collection {
  func position(before p: Position) -> Position
}

struct Slice<T: Collection> {
  let base: T
  let start: T.Position
  let end: T.Position
}

extension Slice: Collection {
  typealias Position = T.Position
  typealias Element = T.Element

  func position(after p: Position) -> Position { base.position(after: p) }
  subscript(p: Position) -> Element { base[p] }
}

extension Slice: BidirectionalCollection where T: BidirectionalCollection {
  func position(before p: Position) -> Position { base.position(before: p) }
}

func demo<T: Collection>(xs: T) -> Bool {
  xs.sameElements(other: xs[xs.start, xs.end])
}
1 Like