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

[alvae]

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.

[BalmungSan]

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.

[sangamon]

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).

[Odersky]

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.

[Odersky]

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

[sasha2048]

@sangamon

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).

Now I understand that I have exactly the same question.

[alvae]

@sasha2048

Now I understand that I have exactly the same question.

Then you’re both in luck because I have written a whole article about it: Generic programming with type classes · GitHub

[sasha2048]

First, a small comment

Note: I think it’s quite unfortunate that I can’t refer to inner classes in the generic signature of a type. I would have preferred to keep CustomListIterator in the scope of CustomList so that it could refer to Node without needing a base. Instead, I had to break the encapsulation of my list’s implementation

You can do like this:

final class CustomList[Element]
    extends Sequence[Element, CustomList.Iterator[Element]]:
  private final class Node(val value: Element, val tail: Option[Node])
  // ...
  def makeIterator(): CustomList.Iterator[Element] =
    CustomList.Iterator[Element](this, head)
object CustomList:
  final class Iterator[Element] private[CustomList] (
      private val base: CustomList[Element],
      private var head: Option[base.Node]
  ) extends AbstractIterator[Element]:
    //...

or even like this:

final class CustomList[Element]
    extends Sequence[Element, CustomList[Element]#Iterator]:
  private final class Node(val value: Element, val tail: Option[Node])
  // ...
  def makeIterator(): Iterator = new Iterator(head)
  final class Iterator private[CustomList] (private var head: Option[Node])
      extends AbstractIterator[Element]:
    // ...

Also there are two small typos

(I'm saying that not to attack, just these are the things I've noticed anyway, so why not to help in fixing them.)

• def lexicographicallyPrecedes[E <: Comparable](a: Sequence[Int], b: Sequence[Int]): Boolean =

  You probably meant (a: Sequence[E], b: Sequence[E]), not (a: Sequence[Int], b: Sequence[Int]).

• def allSatisfy[S: Sequence](items: S predicate: (S.Element) => Bool): Boolean =

  Comma is missing between S and predicate.

The main thing

I’ve read you article before, and have re-read it more carefully just now. Maybe I’m stupid, but it doesn’t fully convince me that explicit typeclass parameters are evil.

Per my opinion, ideally, we should have typeclass parameters explicit. E.g.:

trait Parser[Self, Input, Result]:
  // ...
type ParserAux[Input, Result] = [Self] =>> Parser[Self, Input, Result]
final case class Combine[Input, A: ParserAux[Input, ?], B: ParserAux[Input, ?]](
    a: A,
    b: B
)
given [
    Input,
    AResult,
    BResult,
    A: ParserAux[Input, AResult],
    B: ParserAux[Input, BResult]
]: Parser[Combine[Input, A, B], Input, (AResult, BResult)] with
  // ...

We also can wire typeclass parameters into members. Theoretically that should provide us both advantages: explicit typeclass parameters and shorter further declarations. E.g.:

trait Parser[Self, _Input, _Result]:
  type Input = _Input // I wish there was a syntax sugar for that
  type Result = _Result
  // ...

// Now Combine can be declared shorter:
final case class Combine[A, B](a: A, b: B)(using
    A: Parser[A, ?, ?],
    B: Parser[B, A.Input, ?]
)

But practically that works not always, for example, the following gives an error:

given [A, B](using
    A: Parser[A, ?, ?],
    B: Parser[B, A.Input, ?]
): Parser[Combine[A, B], A.Input, (A.Result, B.Result)] with
  // ...

The type of a class parent cannot refer to constructor parameters, but Parser[Combine[A, B], given_Parser_Combine_Input_Result_Result.this.A.Input, (given_Parser_Combine_Input_Result_Result.this.A.Result, given_Parser_Combine_Input_Result_Result.this.B.Result)] refers to B,A

Still, I like explicit typeclass parameters more from theoretical perspective. IMHO, it would be better if Scala maintainers worked specifically on the problems that complicate usage of explicit typeclass parameters (e.g.: “[X: Y[A, B, C]]” → “(using Y[X, A, B, C]”) syntax sugar, “trait Y[type A] {…}” → “trait Y[_A] {type A = _A; …}” syntax sugar, the aforementioned error, * as “the remaining type arguments are ?”, named type arguments, etc), than on typeclasses that are based purely on associated types. But, of course, that’s just my opinion (based on my own model).

Anyway, thank you very much, now I better understand your vision.

[alvae]

Thanks a lot for your suggestions! I haven’t thought about companion objects (which proves the disclaimer of the article wasn’t lying when it said the author probably missed Scala idioms.)

I updated my document.

@sasha2048

but it doesn’t fully convince me that explicit typeclass parameters are evil.

The problem to me is really about ergonomics, which I rank at least as high as theoretical aesthetics. To set the stage, let me draw a silly comparison. Imagine I ask “how can I use a higher-order function?” in a C users forum and then I get this answer:

#include <stdio.h>

typedef struct {
  void (*f)(void*, void*, void*);
  void* e;
} Function1;

void apply(Function1* a, void* i, void* o) { a->f(a->e, i, o); }

void add(void* e, void* i, void* o) {
  int t = *((int*)i);
  *((int*)o) = t + *((int*)e);
}

int main() {
  int one = 1;
  int res = 0;
  Function1 increment = { &add, &one };
  apply(&increment, &res, &res);
  apply(&increment, &res, &res);
  printf("%i\n", res); // 2
}

Well, I guess I could say that technically that’s possible, but somehow I’ll leave the discussion missing Scala very hard. This example is a bit extreme but my problem with generic programming and type classes in Scala is at least somewhat similar.

I’ll use the term “concept” here the same way I used it in my article. A concept denotes a generic abstraction, like a sequence, which has been lifted from concrete data structures, like a linked-list. I’ll also use the term “associated type” to denote any abstract type that is related to a concept. For example, the element type of a sequence is an associated type.

Now, the style of programming that I enjoy writing lets me, ergonomically and without loss of efficiency:

1. Opt-in or opt-out a conformance relationship. At any time I can state that M implements C (or retract such statement) without requiring any change in any other type. Further, I can do that even if I’m neither the author of M nor C.
2. Conditionally state conformance. I can say that M[X] implements C iff X is equal to N or conform to some composition C1, ..., Cn.
3. Write algorithms solely in terms of concepts and their associated types.

There are other things I could add on the list, but those are the three main requirements.

I’d like to enjoy this specific style of programming in Scala. However, the traditional way of constructing abstractions using inheritance does not fit the bill. That is, if we define Combinator not as a type class but merely as a trait or abstract class with generic parameters, then requirements 1 and 2 are not supported.

If we examine type classes, then supporting requirement 3 gets thorny, no matter how you represent the associated types. Your own examples exposed some of the thorns. My original question did too.

I presented this example to several Scala veterans and got various leads. The most promising one was to use refinements, but this approach broke after I pushed too hard. The one with the ad-hoc “Aux” type looks barely better than my C implementation of Function1 to me. Your second example is a little better (although I didn’t understand it fully) but then the errors you got seems like showstoppers.

I don’t want to argue too hard for a particular solution and in fact the purpose of this thread was to get one already established in the community. I guess I got my answer(s), but I still miss Swift very hard.

@sasha2048

Still, I like explicit typeclass parameters more from theoretical perspective.

What theoretical aspect of the parameters do you find attractive?

As a general observation, I find that having to re-construct generic abstractions from their associated types in all signatures is really poor ergonomics. I think that allStatisfy is a good minimal example:

def allStatisfy[E, I <: Iterator[E]](
    items: Sequence[E, I],
    predicate: (E) => Boolean
): Boolean

The whole purpose of an abstraction, IMO, is to free the user from having to think about all implementation details all the time, whether we’re abstracting over types or values. So I don’t want to have to care about a possibly unrelated associated iterator type when I’m documenting, testing, or using a method that is about a sequence and its elements.