Bounded type as "Companion Object" for type classes

Language Design
1

Here is my proposal to make working with type classes easier, “using the bounded type as if it had a companion object” (better name TBD).

Currently

So imagine you have the type-class:

trait Summable[T]:
  
  def zero: T

  extension (x: T)
    def + (y: T): T

An instance would then look like:

given [U]: Summable[List[U]] with
  override def zero = List()
  
  extension (x: List[U])
    override def + (y: List[U]) = x ++ y

Okay, now let’s try to use it to make a sum method:

def sum[T : Summable](seq: Seq[T]) =
  seq.fold(???.zero)(_ + _)

As you can see, we can’t access zero, it’s not in scope, unlike +.

We can solve this by … not using a context bound:

def sum[T](seq: Seq[T])(using ev: Summable[T]) =
  seq.fold(ev.zero)(_ + _)

Or by cleverly not using a context bound:

def zero[T](using ev: Summable[T]) = ev.zero

def sum[T : Summable](seq: Seq[T]) =
  seq.fold(zero)(_ + _)

And it’s hard to be sure visually that that zero is really related to Summable.
This is especially the case since we could have a val named zero, and overloading would pick for us.

As I’ve hopefully demonstrated, the current solution works, but is not very satisfying, adding potentially confusing boilerplate.

My proposal

Here is my proposal; to be able to access the members defined by case classes by using their argument type as if it was a companion object:

def sum[T](seq: Seq[T])(using Summable[T]) =
  seq.fold(T.zero)(_ + _)
// or
def sum[T : Summable](seq: Seq[T]) =
  seq.fold(T.zero)(_ + _)

It is also possible to restrict that feature to only context bounded types.
This avoid cases where the type is not just an identifier, for example:

def sum[T](p: Seq[(T,T)])(using Summable[(T,T)]) =
  seq.fold((T,T).zero)(_ + _)

And the downside is minimal, as if we’re already using a using parameter, we can name it to access it’s fields.
For these reasons, I feel restricting the feature thusly is advisable.

If I remember correctly, it is possible to do [List[_] : Summable], as I’m not sure what to do in that case, it might be better to forbid that feature on these cases.

Alternative

It is also possible to automatically create synthetic forwarders like:

def zero[T](using ev: Summable[T]) = ev.zero

But not having any prefix on the members makes it hard to track where they come from, with the “type as companion object”, we know it has to come from a context bound (or potentially a using).

8 Likes
2

I’m a big fan of this idea. I’ve often wanted something similar but was thinking of it with a sightly different syntax:

def sum[T : Summable(s)](seq: Seq[T]) =
  seq.fold(s.zero)(_ + _)

I’ve thought of it as sort of visually akin to an unapply. In the case of a using clause, I likely wouldn’t do anything special since it is nearly trivial to just add whatever name you want in the parameter list. So my form above would be equivalent to:

def sum[T](seq: Seq[T])(using s: Summable[T]) =
  seq.fold(s.zero)(_ + _)

My assumption has been that once I give up and type out a full using clause, naming it isn’t a big deal.

3

Honestly, I find this less intuitive than the current using ev: Summable[T] version. The zero comes from Summable, not from T itself, so this starts approaching the “too magical” line IMO.

Yes, it’s a tad less boilerplate, but I don’t think it’s as clear. The boilerplate is a helpful breadcrumb to understand what’s going on.

4 Likes
4

warning: bikeshedding

what about:

def sum[T : ev@Summable](seq: Seq[T]) =
  seq.fold(ev.zero)(_ + _)

?
edit: ah, there was something somewhat similar, but still different.

5

What about this case?

trait Eq[T]:
  extension (x: T)
    def =:= (y: T): Boolean

def hasZero[T : Summable : Eq](seq: Seq[T]) =
  seq.exists(_ =:= T.zero)

Is T now an instance of Summable[T] & Eq[T]? In the simple case you could have easily explained it as a desugaring to def sum[T](seq: Seq[T])(using T: Summable[T]) but here that doesn’t work anymore and really is magical.

6

You look for members zero in both Summable[T] and Eq[T], then overloading resolution applies, and fails at compiletime accordingly.

7

Yes, but T “is a” Summable, in the same way that when x: Int x is an Int, so it makes sense for it to hold the member.

The problem with this syntax is that it stops us from ever adding term arguments to types, something like:

opaque type Vector[T](length: Int) = FixedSizeList[T, length.type]

I’d be more in favor of this, but it’s a bit of a shame to introduce an identifier for this.

Maybe I should have made this clearer, but this was done in the idea to decouple more type classes from implicits, as the link between them is just an implementation detail.
(Many languages have type classes without implicits.)

8

There was discussion offline about using as

def foo[T: Summable as T] = ???
9

I think by far the most straightforward way to achieve this is to change the naming of the evidence parameters generated from context bounds. The evidence parameter corresponding to a context bound [X: T] would be named X. That’s it! As @Jasper-M notes, If we have multiple bounds, we can do that trick only once (for the first bound). That’s probably still sufficient in practice. Multiple bounds are rare and one can usually arrange things so that only the first is needed as a prefix.

As a complement we could also look into ways how we can generate aggregate context bounds. I.e. given (a: A) and (b: B), can I generate evidence for the type A & B? That’s not straightforward, but if we manage to do it, it could be very useful.

9 Likes
10

Maybe a crazy idea, but with NamedTuples, perhaps the evidence parameters could be selected through an aggregated named tuple,e.g., T.Summable, T.Pure, etc.

11

Citation needed :upside_down_face:

Seriously though, this is highly dependent on the coding style.

I do like the idea though, and I think it could generally work with a slight modification.

Instead, name the generated evidence parameter according to the typeclass name, grabbing only the capital letters:

  • [X: Eq] would become (using E: Eq[E])
  • [F[_]: ApplicativeThrow] would become (using AT: ApplicativeThrow[F])

I’ve been doing this manually for a while now, and it works rather well.

Aside: the other reason I really like this idea is because could turn this error message “parameter value evidence$3 in method foo is never used” into “given parameter value R in method foo is never used”, which means I don’t have to remember that evidence$N is 1-based instead of 0-based when counting parameters :slight_smile:

2 Likes
12

I’d add that there is precedent in other programming languages pushing in this direction. Although the support for type classes is based on a different mechanism in Swift and Rust, these languages let you access the contents of an evidence T[X] by talking about X. For example in Swift:

protocol Summable {
  static func zero() -> Self
  static func + (l: Self, r: Self) -> Self
}

func sum<T: Summable>(_ s: Array<T>) -> T {
  s.reduce(T.zero(), +)
}

// Or even more generic! Note that `Sequence` is a type class too.
func sum<S: Sequence>(_ s: S) -> S.Element where S.Element: Summable {
  s.reduce(S.Element.zero(), +)
}

I can’t offer a citation but I can use my experience developing multiple generic libraries that use type classes exclusively instead of subtyping (including an entire standard library) to say that indeed, multiple bounds are rare. What we end up doing in most cases is to create refinement hierarchies. So we’re likely to write something like (using BidirectionalCollection[X]) rather than having separate concepts.

There aren’t so many concepts that are truly unrelated and make sense to combine in a single generic algorithm. In my experience, this situation often indicates that the algorithm has grown too large and must be decomposed or that the concepts must be grouped because they are overly specific.

Of course there are exceptions to every rule :wink:

3 Likes
13

That looks very close to re-inventing an already existing syntax:

def foo[T](using T: Summable[T]) = ???

which very naturally scales from the anonymous variant

def foo[T](using Summable[T]) = ???

Since we have both of these available, the syntax [T: Summable] seems unnecessary to me.

2 Likes
14

that’s because you haven’t considered the possibility of creating a whole new constraints syntax for expressing complex context bounds (i.e not easily expressible with standard parameters) see Improvements to Type Classes by odersky · Pull Request #19395 · lampepfl/dotty · GitHub

1 Like
15

Looks really cool !

16

Maybe I’m wrong, but my comment for PR 19395 is…

 
To be honest, I would rather prefer one of the following things instead of type Self:

  1. Variant A:

    def f[T: Requirement[X, Y]] = ???

    is automatically desugared into

    def f[T](using T: Requirement[T, X, Y]) = ???

    when Requirement[T] is not available (but Requirement[T, …] is).

  2. Variant B:

    Possibility to declare a trait (or class, case class, enum, etc) like:

    trait Requirement[T][X, Y] {…}

    instead of

    trait PreRequirement[T, X, Y] {…}
type Requirement[T] = [X, Y] =>> PreRequirement[T, X, Y]

 
There also could be additional sugaring (inspired by arturopala): type trait Requirement[X, Y] {…} (which would be automatically desugared either into trait Requirement[Self, X, Y] {…} or into trait Requirement[Self][X, Y] {…}, depending of whether we choose A or B) – however that’s non-primary thing.