Create an instance of a type class with methods depending on type members

Question
1

I have the following type class and classes:

/// A parser combinator.
trait Combinator[T] {

  /// The context from which elements are being parsed, typically a stream of tokens.
  type Context
  /// The element being parsed.
  type Element

  extension (self: T) {
    /// Parses and returns an element from `context`.
    def parse(context: Context): Option[Element]
  }

}

final case class Apply[C, E](action: C => Option[E])
final case class Combine[A, B](first: A, second: B)

Now my goal is to create type class instances for my two case classes. I managed to create one for Apply:

given [C, E]: Combinator[Apply[C, E]] with {
  type Context = C
  type Element = E
  extension(self: Apply[C, E]) {
    def parse(context: C): Option[E] = self.action(context)
  }
}

Sadly I’m really struggling with the type checker when it comes to the second one. I’ve got this far:

given [A, B](using
    f: Combinator[A],
    s: Combinator[B],
    q: f.Context =:= s.Context
): Combinator[Combine[A, B]] with {
  type Context = f.Context
  type Element = (f.Element, s.Element)
  extension(self: Combine[A, B]) {
    def parse(context: Context): Option[Element] = ???
  }
}

For context, I’m trying to write a mini parser combinator library to learn about type classes in Scala. Apply is a combinator that just applies a closure and Combine is one that concatenates the results of two other combinators. So my goal is to say that:

  1. There is an instance of Combinator for Combine[A,B] where there exist instances of Combinator for both A and B
  2. The instance requires that both A and B share the same type member Context

The code above compiles but it is seemingly unusable. For example:

@main def hello: Unit = {
  val source = (0 to 10).toList
  val stream = source.to(mutable.ListBuffer)

  val n = Apply[mutable.ListBuffer[Int], Int](s => s.popFirst())
  val m = Combine[A, A](n, n)

  m.parse(stream) // type mismatch, found `mutable.ListBuffer[Int]`, required `?1.Context`
}

I would be grateful if someone could give me pointers.

Hopefully having a kind of realistic use case will make my question clearer, but I’m happy to write a smaller example if necessary.

2

Not sure if there is a simpler way to do this, but basically you want to use the aux pattern to better refine the types and help type inference.

Full code here: Scastie - An interactive playground for Scala.

1 Like
3

Just curious: What’s the use case for type members? AFAICS so far this could just be Combinator[T, C, E], i.e. plain generics, without type members (and Aux pattern).

1 Like
4

I agree with @BalmungSan: The Aux pattern is the best way to support this currently, unless one wants to parameterize everything.

The problem in the original code arises since

 Combine[A, A](n, n): Combine[A, A]

That is, the information about what the argument to the constructor was gets lost. The Aux construction preserves that knowledge.

It would be interesting to see what’s the best way to refine Scala’s typing rules to preserve the lost knowledge directly, without having to go through the Aux pattern.

5

See Experiment: Add `tracked` modifier to express class parameter dependencies by odersky · Pull Request #18958 · lampepfl/dotty · GitHub for possible solutions.