Encoding type class hierarchies

Language Design
1

Hello,

First off, what a beautiful achievement Scala 3 is. I think the huge amount of efforts you have been putting on this project (over the past, what, 8 years?!!) is just incredible and the result is a language that is much more elegant and easy to understand.

I wouldn’t write just to congratulate you though :sweat_smile: so I hope you will forgive me for expressing a gripe I have with one particular aspect. If you look up how to implement type classes in the Dotty documentation, there are a couple of examples where hierarchies are defined as such:

trait BaseClass[X]:
  ...

trait SubClass[X] extends BaseClass[X]:
  ...

It is implied above that type class hierarchies are the same as class hierarchies. This seemingly natural assumption leads, imho, to extremely ugly code and terrible practices downstream, and goes against the “intent over mechanism” mantra. This gets very clear when we look at the problem of writing type class instances:

  1. For any type X, a single instance must be defined for the most specific type class this type can be installed in. This is almost an invariant that is imposed by the mechanism. To take a trivial example from the Dotty website, one can define a Monoid[List] but is almost forbidden to write a Semigroup[List]. If they do, they will not only have to duplicate a lot of code, but it will fall on the user to make the right incantation of imports that pleases the compiler.

Continuing on the same example, it does not make the life of type class authors easier. Let’s look at cats (this is the same problem everywhere):

  1. You won’t find a Monoid[Int]. Nope, you will need to look for CommutativeGroup[Int]. For deep class hierarchies, that doesn’t scale well, as it forces the author to bundle all type class members into one single object. The mental burden that is implicit there goes against the usability given (no pun intended) by the syntactic devices you designed to make users’ life easier at the use site.
    And it gets ugly real quick, as it makes the code less modular, harder to scan and also much harder to find. People who might want to learn why [A] =>> Either[E, A] forms a Functor by studying the code are in no luck, they will first have to find out that it is above all a MonadError.

Speaking of finding, the next problem is to decide where to place your instances. The scenario where one defines their own data type is pretty much solved, if you can live with the above, but what about the rest?

  1. You have two choices which are again entirely mechanism-based. First, lexical scope, the current solution of choice in both cats and scalaz, where the onus is on the user to find the right combination of imports (granted, the dotty compiler provides really helpful messages here).
    Or, use implicit scope, conjure up a diagram in your head and move all your most-specific instances upstream, into the most-generic type class’s companion object. This is the approach adopted by zio-prelude. If you were to look for the Traversable[List], you’d be forgiven to think you would find it in the Traversable companion: no, it is in the companion of Invariant, the root of the hierarchy.

I am sure there are many other annoying consequences to this simple design decision; I think it is clear from the above that it forces developers to hack around semi-solutions to please the compiler in order to limit the burden on the end user.

To come back to the original “intent over mechanism” schtick, i’d like to suggest the following formulation is the only one that makes sense:

trait BaseClass[X]:
  ...

trait SubClass[X](using ev: => BaseClass[X]):
  ...

This to me communicates that a SubClass for X implies the existence of a BaseClass for X. And it seems to me that it solves all the problems I mentioned, just by reading the declaration.

  1. Now I can install short and easy to read instances for List as a Semigroup and also as a Monoid, though I can only do the latter because the former is there. Isn’t that the the whole point? Even better, I can provide a lower-priority instance of Functor[A] from Monad[A] if I want to, because the implicit proof is lazy:
object Monad:
  given functorFromMonad[F[_]](using Monad[F]) as Functor[F]:
    def map[A, B](f: A => B) =
      fa => fa.flatMap(a => summon[Monad[F]].pure(f(a)))
end Monad

2 and 3 are immediately solved too, as there is no incentive to place instances anywhere else than where they make sense: in the companion of the specific type class.

I have been playing with the encoding above, and it makes writing type class hierarchies much more elegant and idiomatic. The only downsides that I have found so far are:

trait Semigroup[A]:
  def combine: (A, A) => A
  extension [A](x: A) def <> (y: A): A = combine(x, y)
trait Monoid[A](using ev: => Semigroup[A]):
  def empty: A

then I could not do something like

trait Applicative[F[_]](using ev: Functor[F]):
  def pure[A]: A => F[A]
  def zip[A, B]: (F[A], F[B]): F[(A, B)]
object Applicative:
  given tupleApplicative[X: Monoid] as Applicative[[A] =>> (X, A)]:
    def pure[A] = (summon[Monoid[X]], _) // works
    def zip[A, B] = (x, y) => (x._1 <> y._1, (x._2, y._2)) // breaks, <> does not exist

I would have to add a Semigroup context bound too. Still, these seem like very small sacrifices compared to all of the above, and I’m not a compiler write but they sound like not insurmountable problems :thinking:

Right, apologies for this long tirade, I had to get it off my chest and submit it to you, in the hope that either I have failed to see something obvious or there is some real potential in the above.

11 Likes
2

This a bold and thought provoking proposal.

My initial worry would be that it would make working with Type Classes in Scala even more complicated than it is today. The implicit mechanism, which is used for derivations is already complex as it is and causes grief, especially to newcomers. Using it also for Type Class extending would aggravate this issue. Subclassing, traditionally used for extending, is much simpler. Even though Scala doesn’t have Type Classes/“traits” as an explicit feature, I feel that the Scala authors intended us to do them this way. That’s why the scheme outlined in Implicit scope and Cats is probably the best we can do, even though it has its issues (instances are in surprising places, non-deterministically chosen if a Type Class inherits from multiple other, …).

It’s also worth noting that, if I understand it correctly, other languages, like Rust or Haskell, do Type Class extensions in ways that are analogous to the traditional subclassing in Scala. I would also guess that they do it the Implicit scope and Cats way, no?

But I don’t want to discourage you, maybe you’re onto something! This idea definitely doesn’t deserve to fall of the table. I would be best, if other, more experienced Scala masters, who have been around longer than me, could chime in :pray: AFAIK this is not the first proposal for different encoding of Type Classes, there’s been scato and maybe others that haven’t even heard of. Only deeper experimentation and experience of Scala veterans could help us determine the pros/cons of this encoding.

2 Likes
3

I’ve found a solution for problem 1: just use abstract classes. If we forgo inheritance, there is no reason to use traits anymore. So this works:

abstract class SubClass[X](using ev: => BaseClass[X])
  ...

I’m just quoting the official documentation for maximum effect:

It is a standard recommendation to prefer composition over inheritance. This is really an application of the principle of least power: Composition treats components as blackboxes whereas inheritance can affect the internal workings of components through overriding.

I have a partial solution for problem 2: export clauses. This works:

abstract class Semigroup[X]:
  def combine: (X, X) => X

abstract class Monoid[X](using ev: Semigroup[X]):
  export ev.combine
  def empty: X

def foldM[A](xs: List[A])(using M: Monoid[A]): A =
  xs.foldRight(M.empty)(M.combine)

However, there are four caveats:

  1. extension methods are not exported

Even though this compiles

abstract class Semigroup[X]:
  def combine: (X, X) => X
  extension (x: X) def <> (y: X): X = combine(x, y)

abstract class Monoid[X](using ev: Semigroup[X]) =
  export ev.{ combine, <> } // the extension method is exported
  def empty: X

This does not:

def foldM[A](xs: List[A])(using M: Monoid[A]): A =
  xs.foldRight(M.empty)(_ <> _)
[error] -- [E008] Not Found Error: /Users/regiskuckaertz/code/zio-prelude/core/shared/src/main/scala-dotty/zio/prelude/xp/Identity.scala:59:41 
[error] 59 |    xs.foldRight(M.empty)(_ <> _)
[error]    |                                       ^^^^
[error]    |value <> is not a member of A, but could be made available as an extension method.

This is a bummer, as one would have to duplicate the extension methods. Perhaps a bug?

  1. I had to pass the given by-value instead of by-name

Otherwise the compiler complains that ev is not stable:

[error] 21 |  export ev.*
[error]    |         ^^
[error]    |(Monoid.this.ev : => zio.prelude.xp.Semigroup[A]) is not a valid import prefix, since it is not an immutable path

This I feel is understandable knowing a little how by-name parameters are elaborated under the hood. If only Scala had first-class support for by-need parameters :thinking:

  1. I had to be explicit with what was exported

Otherwise a weird error came up:

[error] 22 |  export ev.*
[error]    |            ^
[error]    |            no eligible member * at Monoid.this.ev

Again, perhaps a bug?

  1. Dependencies are pushed at the instance definition site

So, to translate this:

Semigroup a => Semigroup (b -> a)
Monoid a => Monoid (b -> a)

you effectively need to do this:

Semigroup a => Semigroup (b -> a)
Semigroup a, Monoid a => Monoid (b -> a)

Despite all of this, I still feel like this is a much cleaner way of expressing the same intent and is also more powerful. For instance the definition of Semigroup a => Semigroup (b -> a) in the inheritance-based model would put both the library author and the library user in a sea of trouble.

oh, how did you come to that conclusion? I tried a very small subset of ZIO prelude, defining Associative and Identity for Chunk:

abstract class Associative[A]:
  def combine(l: => A, r: => A): A

object Associative:
  def make[A](combine0: (A, A) => A): Associative[A] = ...

  given [A] as Associative[Chunk[A]] =
    Associative.make(_ ++ _)

  given [A, B: Associative] as Associative[A => B] =
    Associative.make((f, g) => x => f(x) <> g(x))

abstract class Identity[A](using ev: Associative[A]):
  export ev.combine
  def identity: A

object Identity:
  def make[A: Associative](identity0: A): Identity[A] = ...
  
  given [A] as Identity[Chunk[A]] =
    Identity.make(Chunk.empty)

  given [A, B: Identity: Associative] as Identity[A => B] =
    Identity.make(_ => Identity[B].identity)

This is pretty close to how you would do it in Haskell (idk about Rust though).

5 Likes
4

Oh! Interesting. I was actually totally wrong on this. As you’re correctly pointing out, in Haskell (and Rust), the implementation for separate sub-classes/sub-traits is provided separately, not in one place as Scala/Implicit scope and Cats nudges us towards. (I would then guess that the final dictionaries with all the methods are created by the Haskell/Rust compiler, on the fly during compilation, from the dispersed implementations provided by the programmer.)

Your proposal is thus very very close to how Type classes are done in Haskell and Rust :+1:
It seems like I’ve been projecting my Scala-biased thinking onto those two languages :laughing:

1 Like
5

erf, caveat 3 is my mistake as I used the wrong wildcard character:

export ev._

works

1 Like
6

erf, I must have tested with an older release as caveat 1 does not hold anymore with M3. This is quite exciting! I took a small slice of Scalaz and rewrote it with this paradigm:

I really like how concise it is to define instances. As an author, I do not have the cognitive burden of doing SubClass ~> SuperClass translation in order to write/find them: that is completely gone. Nor do I need to put that burden on end users/future collaborators/students, etc.

Furthermore:

  • inheritance replaced with export directives makes intent declarative. Goodbye diamond hierarchies, now I can selectively export the implementations that I want. Case in point Monad:
abstract class Monad[F[_]](using ev1: Applicative[F], ev2: Bind[F]):
  export ev1._
  export ev2.{ bind, join }
end Monad

where both ev1 and ev2 export members of Apply, but they could well each have their own implementation that I’d have the luxury of choosing.

  • as alluded above, extension methods are also exported, that saves a lot of boilerplate:
abstract class Semigroup[A]:
  def append(x: => A, y: => A): A
  extension (x: A) def <> (y: A): A = append(x, y)

abstract class Monoid[A](using S: Semigroup[A]):
  export S._
  def zero: A

given ListFoldable: Foldable[List] with
    def foldMap[A, B: Monoid](f: A => B): List[A] => B = 
      _.foldLeft(zero)((b, a) => b <> f(a))

This is looking really promising.

6 Likes
7

By the way, there are alternative takes on Type Classes in Haskell too, e.g.

Maybe they contain some ideas that could help us with improving type class encoding in Scala.

8

I’m hoping to revive the effort on this, so this is my attempt at making some progress.

I think I solved most problems with the original approach, this for example works now:

def eq[A: Ord](left: A, right: A) =
  left === right

where === comes from Eq, a base class of Ord.

Also, when declaring an instance for a class that is part of a larger hierarchy, it is only necessary to specify the direct parent instance:

given[A: Ord]: Ord[Wrapper[A]](resolve) with
  def compare(left: Wrapper[A], right: Wrapper[A]): Ordering = 
    left.value =?= right.value

But most importantly this works too!

def infamous[F[_]: Monad: Traversable](fa: F[Int]) =
  fa.map(_ + 1)
  summon[Functor[F]]

The repo with the code is here: GitHub - roald-di/classy-types.

However, there are still a couple of problems:

  • Declaring a typclasses requires a bit of unintuitive boilerplate, and adding support for a new kind of typeclass (e.g., Eq, Functor, BiFunctor, FunctorK, etc…) requires a fair amount.
    The usage and the declaration of instances though remain nice and simple, like in the original.

  • Extensions can’t be declared on the typeclass trait directly but have to be brought into scope some other way (I made them top level definitions).
    This is because in the infamous example above two copies of map would be brought into scope making them ambiguous.

  • This is now pretty similar to the scato encoding so whatever was wrong with that probably applies here as well, but I can’t find much info on it.
    The thing this improves on is extensibility of the hierarchy by the user of the library, and it removes the need to import subclass-to-baseclass conversions explicitly.

  • The case were a subclass provides implementations for methods of a baseclass (e.g., implementing applicative with bind) needs some design work.

One of the difficulties I faced was that once there is an automatic conversion from the subclass to the baseclass, say for example from Ord to PartialOrd,
the baseclass parameter of the constructor cannot be made implicit.
If it were, and an implementation for the baseclass were missing, scala would use the implicit that is currently being defined as a baseclass and pass it to itself.
This would compile but cause an infinite loop at runtime.
The only way I could think of solving this is with the resolve macro seen above, it basically works like summon but will hide the conversion.
If an instance is missing it will fail to compile with an error message like Could not resolve typeclass instance PartialOrd[Int].

1 Like
9

This is awesome, really glad you looked into it.

What I said in the OP was actually a pipe dream. I was hoping for this:

abstract class PartialOrd[-A]

abstract class Ord[-A](using ev: => PartialOrd[A])

object Ord:
  given partialOrd[A: Ord](using NotGiven[PartialOrd[A]]): PartialOrd[A] with
    ???

  given Ord[Unit] with
    ???
    // ^ fails with "no implicit argument of type => PartialOrd[Unit] was found ..."

Even though the documentation seemed to indicate that by-name context parameters would not be evaluated.

Something else that I realised is that if extension methods are defined and users are only exposed to them, the export clauses should not be necessary. Well, that was just a thought, I did not try.

10

I’m not entirely sure what you are trying to achieve, so I apologize if I misunderstood anything.

This is probably a bug, or not, I’m not sure. It’s always hard to tell. :slightly_smiling_face:

// ok
given i(using NotGiven[Int]): Int = 0
given ByValue(using Int): String = ""
summon[String]

// no implicit argument of type String
given i2(using NotGiven[Int]): Int = 0
given ByName(using => Int): String = ""
summon[String]

In the second case it’s finding i2 when looking for NotGiven[Int], in the first it doesn’t.

But even if this were to work wouldn’t it just result in a circular definition? i.e.:


given f: Ord[Unit](using partialOrd(using f, NotGiven.value)) with
  ???

If the goal is to have a default implementation for PartialOrd, maybe a lower priority given could work? something like this:

abstract class PartialOrd[-A]

object PartialOrd extends LowPriority:
  given PartialOrd[Unit] with
    ???

trait LowPriority:
  given partialOrd[A: Ord]: PartialOrd[A] with
    ???

abstract class Ord[-A](using ev: => PartialOrd[A])

object Ord:
  given Ord[Unit] with
    ???

  given Ord[Int] with
    ???

summon[PartialOrd[Unit]]
summon[PartialOrd[Int]]

The export clauses would still be needed to allow

summon[Monad[F]].unit

instead of

summon[Monad[F]].applicative.unit
11

Well, that would be a user mistake :grin: It is weird that it works with functions but not with class instances. See for yourself: Scastie - An interactive playground for Scala.

I guess, but this idea of “lower priority” is not a language feature, it is a compiler implementation leak. If one day the strategy of the compiler changes, all of this breaks. Whereas a declarative expression of intent will always be correct.

You can still declare extensions and do away with the export clause:

extension [A](x: A) def pure[F[_]](using F: Applicative[F]): F[A] = F.unit(x)
12

Lower priority is indeed a language feature. You can see it being refined and improved in Dotty here under point 8, basically at the bottom of the document.

https://docs.scala-lang.org/scala3/reference/changed-features/implicit-resolution.html

You can also find this behavior in the Scala spec: Expressions | Scala 2.13

The relative weight of an alternative AAA over an alternative BBB is a number from 0 to 2, defined as the sum of

  • 1 if AAA is as specific as BBB, 0 otherwise, and
  • 1 if AAA is defined in a class or object which is derived from the class or object defining BBB, 0 otherwise.
2 Likes
13

Fair enough. I stand by my criticism though, the mental gymnastics for reading/writing/maintaining that kind of code is too much. Knowledge in the world vs knowledge in the head, or let’s see what LowerPriority25 has in store for us :laughing:

14

Perhaps I’m clutching at straws here, but I just tried this and found it quite pleasing:

trait Functor[F[+_]]:
  def map[A, B](f: A => B): F[A] => F[B]

trait Apply[F[+_]] extends Functor[F]:
  def ap[A, B](f: F[A => B]): F[A] => F[B]

trait Applicative[F[+_]] extends Apply[F]:
  def pure[A](x: A): F[A]

enum Maybe[+A]:
  case Nothing
  case Just(value: A)

object Maybe:
  given functor: Functor[Maybe] with
    def map[A, B](f: A => B) =
      case Nothing => Nothing
      case Just(x) => Just(f(x))

  given apply: Apply[Maybe] with
    export functor.*
    def ap[A, B](f: Maybe[A => B]) =
      (f, _) match
        case (Just(f), Just(x)) => Just(f(x))
        case _                  => Nothing

  given applicative: Applicative[Maybe] with
    export apply.*
    def pure[A](x: A) = Just(x)

Edit on Scastie

2 Likes
15

For the fans of @regiskuckaertz 's work:

3 Likes
16

I liked the idea and loved the talk.

The labyrinth of base and child types for the typeclasses (in cats) is definitely intimidating for a newcomer and also a cognitive burden.

1 Like
17

I like this, but it’s not clear if there’s a proposal or suggestion to debate. It feels like a suggestion for a new library or a reimagining of cats maybe?

Anyway, I agree with everything from the original post. What is the next step?

18

I’ve tried a new experiment after getting inspired by looking at this image: https://i.imgur.com/1Z2Z2ZQ.png
https://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Algebraic_structures_-_magma_to_group.svg/849px-Algebraic_structures_-_magma_to_group.svg.png

The main idea is to model the arrows instead of the objects.
So for the functor hierarchy we would have something like this:

trait Map[F[_]] extends Typeclass:
  def map[A, B](f: A => B): F[A] => F[B]

trait Zip[F[_]] extends Typeclass:
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)]

trait ZipIdentity[F[_]] extends Typeclass:
  def any: F[Any]

trait Join[F[_]] extends Typeclass:
  def join[A](ffa: F[F[A]]): F[A]

trait JoinIdentity[F[_]] extends Typeclass:
  def pure[A](value: A): F[A]

then we can get the usual hierarchy back by composing the arrows, for applicative we would have:

def useApplicative[F[_]: Map: Zip: ZipIdentity] = ???

This is actually pretty close to what zio/prelude already does.

Unfortunately it would get annoying quickly since scala doesn’t have aliases for type constraints, but we can get close with intersection types and a macro to summon them:

type Functor[F[_]] = Map[F]
type Applicative[F[_]] = Functor[F] & Zip[F] & ZipIdentity[F]
type Monad[F[_]] = Applicative[F] & Join[F] & JoinIdentity[F]

def useApplicative[F[_]: Applicative] = ???

they can also be combined inline with a type alias:

type &&[F[_[_]], G[_[_]]] = [A[_]] =>> F[A] & G[A]

def useMonadTraverse[F[_]: Monad && Traverse] = ???

It’s possible to define constraints with implicit parameters, but they have to be marked as erased since the macro currently doesn’t support trait parameters.
This is probably fine since they are not actually used.

trait Ord[A](using erased Eq[A]):
  def compare(x: A, y: A): Ordering

I can’t upload this to scastie since it requires a macro, but I’ve updated the repo on github:

1 Like
19

@roald-di you might like ZIO Prelude :wink:

https://zio.dev/zio-prelude/functionalabstractions/

20

I do like it! :slight_smile:

however, I think it’s still missing a step which is the ability to declare
instances separately from each other and in the obvious places, which is what regis’s idea is about.

In the example above for instance if you want an AbelianGroup you have to define a single implicit that
implements both Commutative and Inverse and does so in the right order.
If you are implementing it for a scala library type like Int then there is also no a place to put that instance
that allows it to be summoned as either an AbelianGroup or, separately, as a Commutative or an Inverse.

With what I was proposing on the other hand you can place an instance of Commutative[Int] and
an instance of Inverse[Int] in their respective companion objects and then summon[Commutative[Int] & Inverse[Int]] or also

type AbelianGroup[A] = Commutative[A] & Inverse[A]
summon[AbelianGroup[Int]]

zio-prelude also defines monad as

type Monad[F[+_]] = Covariant[F] with IdentityFlatten[F]

But then some instances like the one for Chunk implement IdentityFlatten and Covariant
as two separate implicits, which means you can’t actually summon a Monad for Chunk.
This isn’t meant to criticize anyone working on zio-prelude!
it’s just that making all possible aliases work correctly this way is just too hard in my opinion.