Dotty Type classes


#22

type class would harmonize with case class if not a problem with different inheritance notation. New keyword is also pretty big deal.

as i know extension keyword is planned anyway. instance would be new one.

I’m not big fan of introducing such big chunk of syntax for things that can be encoded with other tools, and are not used super widely. Is there such big need for defining typeclasses?
Creating instances could be more important but still we should try to keep syntax as close current scala as possible.

What about alexknvl more conservative syntax proposition?
I know that it is not exhaustive proposition but maybe it can be polished?


#23

Scala has type members. I still don’t get why those multi-parameter typeclasses don’t use them.

trait Collection[C] { // or whichever syntax you prefer
  type E
}

trait MonadError[F[_]] {
  type E
}

#24

I’m unsure about your wording, since your wording implies you talk about individual call sites, but in general guaranteeing coherence is not possible, especially due to dynamic linking. It’s very hard to guarantee that an Eq[A] wasn’t defined multiple times in any of the project’s dependencies and having such a guarantee in the project’s own source files is a pretty weak guarantee to have.

IMO a warning is enough. Coherence is mostly achieved by convention and that’s OK. Even in Haskell sometimes you just need orphans (e.g. JSON serialization).


#25

Scala has type members. I still don’t get why those multi-parameter typeclasses don’t use them.

Because it doesn’t work. E.g. a type member doesn’t work for MonadError since obviously you can have multiple MonadError instances defined for each (F[_], E) tuple you care about and its behavior can change depending on E. Not many such instances in the wild, but type members and type parameters are apples vs oranges.

And the E type is also exposed in the function signatures, which means you lose type information about it when working with the generic MonadError[F] interface. You can only materialize E when the compiler knows the exact instance you’re using, otherwise the type is going to be MonadError[F]#E, which is pretty useless and annoying.

I’d like to point out that … if we are going to introduce type classes, it’s very important to look at actual usage in the wild. We need multiple type parameter classes, because multiple type parameter classes have been in use for a long time. In Cats-Effect too we have been discussing multi-param type classes in order to accommodate “bifunctor IO” implementations.


#26

Yes, there’s an entire ecosystem that uses type classes, see the projects at Typelevel.org.

Type classes as a concept are equivalent with implicit parameters (which is why Scala is an awesome language for FP) and, in comparison with OOP subtyping, type class restrictions play better with generic type parameters and static typing.

As Luka is explaining, nowadays we have to do a lot of boilerplate in order to encode these concepts. And we can use macros in order to reduce that boilerplate (see Simulacrum), but AFAIK such libraries will no longer be possible on top of Scala 3 / Dotty due to no longer having such macros capabilities.

Book authors like the authors of Scala with Cats have complained that beginners have a really hard time grasping FP concepts due to type classes being so hard to understand due to the extreme boilerplate and ceremony involved.

Scala is a language that has thrived on its HKTs and ability to define and use type classes. That’s one of the features that make Scala shine in comparison with other languages. It’s time to make that official.

And it would be a shame if Kotlin got type classes first.


#27

But you cannot have MonadError instances for any (F[_], E) tuple. For IO it’ll always be Throwable. For IO[E, ?] it’ll always be E. For Either[E, ?] it’ll always be E. And ok, for EitherT[IO, E, ?] I guess it’ll be one of Throwable or E. But it’s still determined by F. For EitherT you’ll just have to give priority to one of both instances, and use an orphan instance if you want to use the other, kind of like when you want a * Monoid instead of the default +.

That’s exactly my point, actually. If one type is determined by the other, I think that a type member is a better fit.

Currently you can use the Aux pattern when you need to be able to know inside your method that e.g. E =:= String. If we’re scrapping boilerplate for typeclasses, you could consider boilerplate free Aux as well.


#28

@Jasper-M You proposal breaks for polymorphic code. Consider this:

def foo[F[_]](implicit F: MonadError[F, Throwable]): F[String] = 
   F.raiseError(new Exception("problem")).handleError {
        case e => e.getMessage
  }

val a = foo[IO]

if you used a type member for MonadError, we’d have:

def foo[F[_]](implicit F: MonadError[F]): F[String] = 
   F.raiseError(new Exception("problem")).handleError {
        case e => e.getMessage // Doesn't compile
  }

because we lose info about which E we are talking about. To recover that you need the Aux pattern

object MonadError {
 type Aux[F, Err] = MonadError[F] { type E = Err }
}

so that we can implicit F: MonadError.Aux[F, E], at which point it’s just better to use two type parameters instead. There are multi param type classes that benefit from type members (cats Parallel for example), but MonadError isn’t one of them imo: it only makes sense to hide E when you are dealing with a concrete type, but in that case you don’t need a typeclass constraint at all, and when you do, you’d have to use Aux anyway, so it really makes more sense to have two type params there.

Note that the example you made in your comment here, i.e.

def bar[F[_]: MonadError](f: F[String]) = ???

Doesn’t really work: polymorphic code that calls bar cannot recover from the error, because it has no information about E unless: F is instantiated to a concrete type (you lose polymorphism), or bar is changed to use Aux (no benefit from having a type member)


Furthermore, there are still cases where a multi param type class still needs two or more type params, even with type members, for example:

class Mult a b c | a b -> c where
  (*) :: a -> b -> c
 
instance Mult Matrix Matrix Matrix where
  {- ... -}
 
instance Mult Matrix Vector Vector where

Here c can be a type member, but a and b make sense as type parameters. Shapeless provides countless real-world examples of this


#29

@scalway

type class would harmonize with case class if not a problem with different inheritance notation. New keyword is also pretty big deal.

If adding a new keyword represents such a big challenge I completely understand. I just wanted to point out how confusing it might sound for newcomers:

  • type: to define type aliases. Eg type Username = String
  • class: to define and instantiate classes. Eg. class Foo() and val foo = new Foo()
  • type class: to define a type classes. Eg. type class Monoid[A] : Semigroup[A] {}

Is there such big need for defining typeclasses?

Yes. As @alexandru pointed out there’s an entire ecosystem making use of them and we would benefit from having an easier way to work with them.

Creating instances could be more important but still we should try to keep syntax as close current scala as possible

Changes are already being made (opaque types, type lambdas, etc) and I think it’s for the better. Keeping syntax as close as current Scala is secondary IMHO.

What about alexknvl more conservative syntax proposition?

His second (more conservative) option looks pretty similar to what we can do today in Scala 2 and I can’t see how type classes syntax could be defined. However, I believe we can do better for Scala 3 by having native support for type classes.

BTW I think it’s great Alex is managing to get that to work in Scala 2 with the scalafix plugin!


#30

Unless I’m missing something it’s a standard compiler plugin, no scalafix involved.


#31

Is there such big need for defining typeclasses?

Yes, absolutely! It is a very common pattern, that has a number of distinct advantages over prior encodings of dictionaries of behaviour, in particular inheritance. Typeclasses are one of the things enabled by Scala that enables principled higher-order functional programming, and all the benefits it provides. Having first-class support for typeclasses will significantly improve the usability of Scala for FP, particularly if coherence and modularity are addressed well.


#32

I think that the (in process) Dotty concepts of transparent (or whatever it gets called) and implicit matching obviate the Aux pattern in at least most cases. (Although I am absolutely not an expert in this end of things.)


#33

I finally got round to read the proposal. It’s very interesting! The idea to use this as a parameter name for an implied receiver is worth looking into. I was wondering what rules you had in mind for name resolution here? I.e. under what circumstances does x.f(y) get expanded to pre.f(x, y) for some implied prefix pre? It would be good to work this out in detail.

The issue of coherence involves a lot of difficult tradeoffs. For me the toughest tradeoff is that in Scala you would have to choose between (global) coherence and orphan instances. You can’t have both. Orphan instances (i.e. type class instances that are neither declared with the type class nor with the instance type) clearly are useful. A typical use case is if you want to retro-actively add serializers to some third-party library. But with orphan instances coherence cannot be checked fully at compile-time. Consequently, Haskell delays some checking to link time. But this is not an option for Scala because on the JVM with lazy class loading, link time = run time. Concretely, if we did coherence checking at run time this would mean that a program could get into some rarely taken path due to error handling that loaded a library that caused a global coherence violation that went undetected until then. Clearly, that’s not what we want. So, how to get out of this dilemma?

I still think we should alternatively take a good look at the ML way of doing things, which is in many respects closer to Scala. In particular, it might be that we could get a modular handle on coherence using applicative functors with sharing constraints. But so far that’s more a hunch than a concrete design.


#34

It might be worthwhile to study how Simulacrum does this translation, and which limitations its implementation still has. That might give an idea how non-trivial this might be.


#35

Thanks for the proposal, it looks nice.

However, I disagree with the rejection of inheritance for defining type classes. The only given justification:

Adelbert Chang wrote a paper describing in great detail why subtyping for type classes is a suboptimal approach.

seems somewhat misled. AFAIU, despite its title (which I find slightly inadequate), the cited paper does not show that subtyping per se has any fundamental limitations for encoding type classes. All it shows is that in the current Scala implementation there is no way to prioritize implicits derived from subtyping, whereas one can prioritize implicit conversions which allows to avoid ambiguity errors… but ad-hoc prioritization is a hack anyways and can lead to surprises in case the instances are truly ambiguous, so it doesn’t really matter.

The real problem is either:

  • to rule out the ambiguity in the first place, and the way that would be done is via coherence. As is mentioned in Chang’s paper, this Dotty ticket shows that it can be done with subtyping;

  • or to have a convenient way to specify which instance the user wants, and for this I have seen different tricks but can’t remember one that doesn’t work with subtyping (though there might well be).

So instead of going with the natural, idiomatic inheritance-based definition approach, your proposal basically duplicates all its features, greatly increasing the surface of the language, but for apparently no good reason.

Please correct me if I’m wrong :^)


#36

I would take orphan instances over coherence.

Coherence is not the problem we have with type class usage thus far. In my opinion at least. It’s a problem to think about for sure, but convention largely works fine. Personally I’ve never been bitten by violations of coherence. I know it probably happens sometimes, but with “opaque types” and education, I think it will be a non-issue.

The problem in the ecosystem is that there will be libraries that don’t want to depend on any particular library of type classes, e.g. Cats or Scalaz, and provide type class instances in separate projects, thus orphans. And the reasons for this can be very valid, like having a “no dependencies” policy for the core.

Orphans are a must. AFAIK GHC allows orphans too and that too can lead to conflicts. But it’s better than the alternative.


#37

A possible feature request: better handling of the special cases induced by case classes. I haven’t used type classes much but really like the idea already. On my recent foray into Scala type classes I came across this problem, which is basically the fact that it is not easy (and there appears no standard way) to require that a case-class-like copy method exists. Maybe there just isn’t a good solution to this problem, but I can see it potentially being very nice from an ergonomics perspective.

Basically, we want to be able to add a type class member copy that can be easily satisfied by a case class’s copy:

trait Foo[F] {
  type T
  def aa(foo: F): List[T]
  def maybe(foo: F): Option[T]
}

final case class Bar(aa: List[String], maybe: Option[String])
object Bar {
  implicit val barFoo = new Foo[Bar] {
    type T = String
    def aa(foo: Bar): List[String] = foo.aa
    def maybe(foo: Bar): Option[T] = foo.maybe
  }
}

#38

@LukaJCB I very much like your proposal. I have a syntax nit and a question.

Syntax Nit

type class CommutativeMonoid[A] : CommutativeSemigroup[A] : Monoid[A]

which to me it looks like the CommutativeSemigroup[A] instance must be a Monoid[A]. I’d prefer something that looks more like intersection.

type class CommutativeMonoid[A] : (CommutativeSemigroup[A], Monoid[A])
type class CommutativeMonoid[A] : CommutativeSemigroup[A] & Monoid[A]

Or in an extreme case

type class A : B : C: D: E

I want to read as

type class A : (B : (C : (D : E)))

So I’d rather write it as

type class A : (B, C, D, E)

Multiple Derivations

Can there can be multiple ways to define a type class? Like suppose I have a type class A, which I can define in terms of type classes B and C in an efficient way, but a default without them would work too? In other words, the following shouldn’t conflict.

type class A

extension simpleA[T]: new A { ... }    
extension fancyA[T: B & C]: new A { ... }

I swear I’ve seen something like this in the Haskell typeclass ecosystem, but it’s been years since I’ve looked at it.


#39

I disagree – this feels (appropriately) like the context-bound syntax for specifying multiple typeclasses. I don’t think it implies anything any CommutativeSemigroup.

I get why you have this intuition, but the proposal seems consistent with the way we usually talk about types in Scala…


#40

I think we can easily keep the subtype encoding of type classes and resolve ambiguity errors at the same time by just narrowing the type signatures of implicit instances.

Let’s ask – what prevents us from choosing an arbitrary instance in case of ambiguity?
It’s only the fact that when we get two opaque implicit values in our implicit search: Monad[F] and Traversable[F], we can’t possibly know if the underlying Functor[F] is the same for both.

If we knew, we could pick either of them. But we could just directly check if they’re the same!

Let’s start with the usual suspects:

trait Functor[F[_]] { def map[A, B](f: A => B): F[B] }
trait Monad[F[_]] extends Functor[F]
trait Traversable[F[_]] extends Functor[F]

trait Maybe[A]
object Maybe {
  trait FunctorImpl extends Functor[Maybe] {
    final def map[A, B](f: A => B): Maybe[B] = ???
  }

  implicit val maybeMonad: Monad[Maybe] = new Monad[Maybe] with FunctorImpl { ??? }
  implicit val maybeTraversable: Traversable[Maybe] = new Traversable[Maybe] with FunctorImpl { ??? }
}

When we try to summon an implicit value, we’ll get an ambiguity error.

  implicitly[Functor[Maybe]] // error

We know that both maybeMonad and maybeTraversable are inheriting the implementation of Functor[Maybe] from FunctorImpl, we also know that map in FunctorImpl is final, so neither of them could override it.
We have ample evidence that both of these implementations are equivalent with respect to Functor, but unfortunately, we hid it from the compiler by widening the type back to Monad[Maybe] and removing the mention of FunctorImpl, let’s fix that mistake:

  implicit val maybeMonad: Monad[Maybe] with FunctorImpl = new Monad[Maybe] with FunctorImpl { ??? }
  implicit val maybeTraversable: Traversable[Maybe] with FunctorImpl = new Traversable[Maybe] with FunctorImpl { ??? }

Or just omit the signatures and let the compiler infer the narowest type:

  implicit final val maybeMonad = ???
  implicit final val maybeTraversable = ???

Now the compiler, too, has direct unfalsifiable evidence that both of the implementations are the same, it only needs to glance at the type signature to verify it. At this point it can safely pick either instance, knowing that they both point to the same trait.

  implicitly[Functor[Maybe]] // good, all the instances are just FunctorImpl in disguise

In more detail, when encountering an ambiguity over some type T, for each ambiguous instance,
the resolver should try to find the latest base class that implements T with all T methods as final, if all found base classes are the same for every instance, the compiler now has direct evidence that all implementations of Tin the search are the same and can pick any of them.
Alternatively, a more exhaustive scheme would be to extract the set of methods of T and verify that for each ambiguous instance, there is a final implementation of each method with the same ‘source’. This would allow two methods of T to be finaly implemented by two different traits, but still correctly disambiguated.

For library authors, the scheme would entail two minor changes to their workflow:

  • they would have to specify the narrowest type for their implicit values, instead of widening them
  • they would have to final their methods

For users of implicit there would be no changes at all – they would just suddenly stop getting ambiguity errors! They wouldn’t have to specify coherence domains in their implicit summons and they wouldn’t lose the ability to declare orphans and local instances.

This scheme does not substitute for coherence in all cases, but it solves the problem of ambiguity in a straightforward and obvious manner without imposing any draconian restrictions on the users.

Implementation: the scheme is a simple enough extension as to be implementable today as an implicit macro or as a compiler plugin.

Caveats: If an implicit value is taken and re-assigned to a variable with a widened type, it’s disambiguation properties are lost. However, coherent domains exhibit the same properties if an implicit in a domain is re-assigned to a domainless value.

A variant of this scheme can also be implemented if Scala gets first-class delegation, e.g:

  final val functorMaybe: Functor[Maybe] = ???

  implicit val maybeMonad: Monad[Maybe] with (Functor[Maybe] by functorMaybe.type)
  implicit val maybeTraversable: Traversable[Maybe] with (Functor[Maybe] by functorMaybe.type)

Would be resolved because the singleton types which implement the Functor class are proven the same.


#41

@kaishh I must say I really like this proposal as a compromise between adding a lot of duplicate type system extensions and achieving the desired outcome.

I also agree with @alexandru w.r.t orphan instances.
They’re a necessary nuisance in my opinion and completely forbidding them would break a lot of people’s code. In the proposal I wanted a way to make it easier to detect bugs when orphan instances are declared instead of outright forbidding them :slight_smile: