Dotty Type classes


#1

From what I can gauge type classes are one of the most requested and most fiercely debated features in Scala.
There’s quite a lot of previous discussion as can be found here, here and here.

This thread is supposed to be a continuation of that discussion though from a different angle.
These discussions come a lot of heat and passion, let’s try not to repeat the previous discussions and keep this as grounded as possible.

Type classes are often seen as a functional programming feature, though I’d argue they’re not really related technically. However in Scala, a very large part of the developers who make heavy use of type classes are also largely users of the more FP side of the community.
In the last couple of months, I’ve tried to talk with as many people as possible to get a good view of what these developers would like to see if Scala were to gain a “native” type class feature.

This is what I consider to be the result of that:

Type classes in Scala should:

  1. Be easy to use (e.g. infix syntax) without requiring a bunch of boilerplate
  2. Support for multiple-parameter-typeclasses
  3. Seamless support for using two different type classes that extend from the same base (e.g. Traverse and Monad)
  4. Better support for coherence (i.e. no two type class instances for the same type should be in scope)

To that end, I wrote a type class proposal that you can read here. It is by no way set in stone and even quite incomplete in some cases, but it might give some insight into the desired features.
I, myself, am not a compiler engineer and can’t really say much about how difficult it would be to introduce these new type checking mechanics, so maybe it would be better to create a more iterative design when we can find consensus for what feature set Scala type classes should be able to support.
I’m completely flexible as far as the details of that proposal go, as long as the feature set is there. I think before we start discussing the exact syntax and implementation, we should discuss the desired features.

I hope we can get some good discussion going and reach a good compromise for all the interested parties. :slight_smile:


#2

I like this proposal a lot! It’s a great distillation of the many excellent ideas proposed in previous discussions.

It has a lot of advantages:

  • The mechanisms involved will be familiar to Kotlin and Rust programmers
  • It’s obvious which methods are eligible candidates for extension
  • It only uses one new keyword
  • It (mostly) reuses the existing syntax for context bounds

I’m going to echo @LukaJCB and urge the thread to avoid getting bogged down in discussion of the syntax :slight_smile:


#3

Question about extension methods-
The example from your proposal:

object Ops {
  extension def **(this i: Int)(j: Int): Int = Math.pow(i, j)
}

Can’t we just use the implicit keyword instead of extension, since we have the new way of using this?

object Ops {
  implicit def **(this i: Int)(j: Int): Int = Math.pow(i, j)
}

I feel it’s more consistent with:

trait Foo
object Foo {
  implicit def fooToInt(f : Foo) : Int = ???
}

#4

Sure, I’m definitely open to that, though as I said earlier, I think we should focus on the features and semantics before talking about syntax :slight_smile:


#5

Sorry, but its one of my bug bears. You use Monoid in the example, but Monoid is not a typeclass, its an operation class, at least in Scala. Multiplication and Addition are both Monoid operations, on Integers, I’m sure if one delved into it one could find more monoid operations for Integer.


#6

Hi @RichType,

Monoid is a type class because any set of functions can be a type class and in Typelevel Cats we decided to have it, see Monoid. And there’s no such thing as an “operation class”.

You have a point that multiplication and addition can both be used to define monoids for integers, however you can also define a multiplication monoid if that’s what you want, you just have to define an opaque alias for Int (aka a “newtype”) and the coherence rule will still hold.

The proposal is not about particular type classes to be added to the standard library though, Monoid was used because it’s a very simple example that drives the point accross.


#7

I would like to add that I think it would be very very nice to support what Rust calls “trait objects” which are basically the typeclass version of dynamic dispatch. That is, I think we should have the ability to deal with collections of data which all have a typeclass instance, where each element may have a different underlying typeclass instance (rather than all elements having the same typeclass instance). See this discussion for further motivation.


#8

yes there are more: min, max, bitwise xor, and, or.

That said, non coherent typeclasses don’t seem to disqualify them in scala (is Ordering a typeclass? what about Ordering.by, how about the fact there are two good choices for Applicative on List?)

To me, dealing with coherence can be done with the opaque types proposal: https://docs.scala-lang.org/sips/opaque-types.html


#10

So I guess the identity value for min is 2,147,483,647.


#11

So while I’ve long wished that Functor and Monad were part of the standard library, but been sceptical of the value of Monoid and Semi Group instances. So I thought I’d see what Cats had to say.

val l = List(1, 2, 3, 4, 5)
l.foldMap(i ⇒ (i, i.toString))
//(15,12345)

Having a default combine operator for String is an even worse idea than for Int. Composing semigroups and monoids seems like a bad idea, because the more monoid instances you compose over the less chance that you actually want all the defaults.


#12

In practice the default instances end up being what you usually want. It’s a pragmatic decision but as a longtime user of this stuff I think it’s the right call. I very seldom want a different one, and when I do I use a newtype and it’s fine.

Note that in some cases like Boolean there’s no obvious way to pick a canonical instance so we just don’t have one.


#13

Just to emphasise the point I’ve changed the values:

val l = List(81, 2, 12, -15, 0, 76, -3)
val l2 = l.foldMap(i ⇒ (i, i.toString))
println(l2) 
//(153,81212-15076-3)

#14

For instances to be coherent they have to be placed either in the companion object of the type class or the companion object of the data type the instance is defined for. We should still allow local instances that can be brought in scope like they can today, but the compiler should at least emit a warning.

This is not enough for coherence. You also need to have an overlapping instance checker.

Here is what I want to see from the orphan checker:

  1. Guarantee that whenever someone implicitly summons a typeclass, it’s always the same instance (coherence).
  2. Being able to do (e: Eq[A]).contramap when declaring implicit instances.
  3. Being able to operate with an a: Eq[A] as if it’s just a record as long as you don’t export it implicitly.
  4. Being able to unsafely turn a: Eq[A] into an implicit val a : Eq[A].

This is considerably better than what Haskell does, because typeclasses become first-class values (for the most part).

It’s sort of TcEq[A] <: Eq[A], where implicits must have type TcEq[A]. Upcasts are free, downcasts are only visible in the companions. You can (a : Eq[A]) : TcEq[A] @orphan (or something to that effect) to unsafely downcast. (TcEq[A] and Eq[A] should be visible to the user as the same type, but from the POV of the typechecker, all implicit val eq: Eq[A] are actually typed as TcEq[A])

Being able to unsafely turn a dictionary into a typeclass gives you reflection / local instances a la https://github.com/ekmett/reflection/blob/master/examples/Monoid.hs (ideally you also need polymorphic values for Rank-2 polymorphism, but we can do without).


#15
type class Semigroup[A] {
  extension def combine(this x: A)(y: A): A
}

type class Monoid[A] : Semigroup[A] {
  def empty: A
}

If a more conservative syntax is used, we might be able to do this with

trait Semigroup[A] extends Typeclass {
  def combine(@this x: A)(y: A): A
}

trait Monoid[A: Semigroup] extends Typeclass {
  def empty: A
}

in Scala2 with scalaz-plugin (https://github.com/scalaz/scalaz-plugin).


#16

I think there shouldn’t be a Monoid for min. Just a semigroup. If you want a monoid, wrap your type in Option. Also, what’s wrong with append as the concat operation for String?

I like the idea of coherent typeclasses and using opaque types for custom instances.


#17

I don’t think it’s fruitful to discuss what exact typeclasses and which variants of them to implement in the Standard Library, at least not in this thread. We should focus exclusively on the feature set of typeclasses in general, to make them easier to define and use in all cases.


#18

Min is a monoid if your type is upper bounded (such as Int.MaxValue, Long.MaxValue, etc…)

It’s actually a BoundedMeetSemilattice: https://github.com/typelevel/algebra/blob/master/core/src/main/scala/algebra/lattice/BoundedMeetSemilattice.scala


#19

Right, now I see there’s even instance (Ord a, Bounded a) => Monoid (Min a) in GHC. My original reasoning was that having a Min for integers in general doesn’t make sense because there’s no representation of integer infinity. Somehow Int.MaxValue still doesn’t sound exactly perfect to me, but I guess it’s the best thing we have :wink:


#20

whether or not Monoids should have a TC representation or not (an interesting topic) is totally orthogonal to TC support in Dotty, and is derailing the discussion of it.


#21

First of all thanks a lot for taking the lead on this proposal @LukaJCB ! I think it is very possible to debate such an important topic in a friendly way let’s keep it up :slight_smile:

Here are some thoughts I have after re-reading the proposal:

Extension methods

Introducing a new extension keyword sounds good to me :+1:

Being able to define extension methods directly in a type class definition sounds great!

Type class definitions

I would rather introduce a typeclass keyword instead of combining the two existing ones type and class because I think that’s confusing for people learning the language. Would this represent a big challenge?

I very much agree that type classes definitions should not permit inheritance. This will tremendously help with coherence.

Not sure having override extension is a good idea but I agree it is sometimes necessary to override default implementations (eg. flatMap) for performance and stack safety reasons but right now I can’t think of any better idea.

Instance declarations

I would rather introduce an instance keyword for this. I find the use of the extension keyword as the valid way to declare type classes instances very confusing since it’s also used to declare extension methods (AKA syntax).

Type class usage

LGTM :+1:

Coherence and multi-param type classes

Overall I think we need more details and examples on this part. AFAIU I think it should be fine if the compiler can determine the type class instance by following the associated types as proposed.