Beginner questions about type classes

[sangamon]

@jducoeur

trait Aggregateable[M[_]] {
  def foldLeft[A,B](m: M)(z:A)(op:(A,B)=>A):M[A]
}

That doesn’t look entirely right.

trait Aggregateable[M[_]] {
  def foldLeft[A, B](m: M[A])(z: B)(op: (B, A) => B): B
}

@jducoeur

Well, it needs to be parameterized over A , so it has to be a def instead of a val (since val s can’t have type parameters).

We don’t depend on the generic type parameter for M in the signature, so it can be a val or, more convenient, an object:

implicit object ListAggregateable extends Aggregateable[List] {
  override def foldLeft[A, B](m: List[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
}

However, this way we’d have to implement a type class instance for each concrete collection. I’ve tried to come up with an instance at TraversableOnce level. (Now requiring a def, indeed.) It kind of seems to work, but…

implicit def traversableOnceAggregateable[T[a] <: TraversableOnce[a]]: Aggregateable[T] =
  new Aggregateable[T] {
    override def foldLeft[A, B](m: T[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
  }

…I have no idea how to interpret/explain the effect of the ‘a’ type parameter. I can’t use ‘_’ instead because then T[A] won’t be accepted as a subtype of TraversableOnce[A], and thus op will be rejected as an argument to #foldLeft(). Any explanation about what’s going on there (or just the proper term(s) to throw at a web search) would be appreciated.

@jducoeur

It seems to me I need to define the treeAggregate method for each of the implicit instances. Right?

No, that’s specifically what we’re trying to avoid. This is all about defining a single typeclass that is sufficient so that treeAggregate can work with any type for which there exists a typeclass instance.

Exactly. The signature would become

def treeAggregate[M[_] : Aggregateable, A, B](objects: M[A], init: B, seqop: A => B, combop: (B, B) => B): B

…and the #foldLeft() invocation would be implicitly[Aggregateable[M]].foldLeft(objects)(...).

[crater2150]

@sangamon

…I have no idea how to interpret/explain the effect of the ‘ a ’ type parameter. I can’t use ‘ _ ’ instead because then T[A] won’t be accepted as a subtype of TraversableOnce[A] , and thus op will be rejected as an argument to #foldLeft() . Any explanation about what’s going on there (or just the proper term(s) to throw at a web search) would be appreciated.

The a here is called a higher-order type parameter in the spec, as it is a type parameter of another type parameter (here: of T)

@Scala Spec

Higher-order type parameters (the type parameters of a type parameter t) are only visible in their immediately surrounding parameter clause (possibly including clauses at a deeper nesting level) and in the bounds of t.

This means the parameter a is visible only inside the parameter list of traversableOnceAggregateable, which the spec says later is the reason, why such parameters are usually replaced with _.

But this isn’t possible, if the parameter is needed in more than one place. Writing T[a] <: TraversableOnce[a] will ensure, that the type parameter passed to T is the same type used for TraversableOnce.

If you used _ for both here, this would introduce two anonymous types. Therefore, an instance T[A] would only be an instance of TraversableOnce[Any] (because we never pass a parameter to TraversableOnce, so the compiler infers Any). This explains the compiler error you get, when you use _:

@ implicit def traversableOnceAggregateable[T[_] <: TraversableOnce[_]]: Aggregateable[T] =
    new Aggregateable[T] {
      override def foldLeft[A, B](m: T[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
    } 
cmd6.sc:3: type mismatch;
 found   : (B, A) => B
 required: (B, Any) => B
    override def foldLeft[A, B](m: T[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
                                                                                   ^

You can see that the foldLeft method now expects a function (B, Any) => B. foldLeft comes from TraversableOnce, so that’s where the wrong Any type must come from.

[jimka]

@jducoeur

No, that’s specifically what we’re trying to avoid. This is all about defining a single typeclass that is sufficient so that treeAggregate can work with any type for which there exists a typeclass instance. The Aggregateable is a parameter to treeAggregate in this design

Perhaps I’m beginning to understand the concept better, but the details are still sketchy. Tell me if this understanding is correct.

1. I need to implement a trait (we are saying Aggregateable) parametrized on some subset (call it S) of the Scala types. As I understand it S is nowhere explicitly defined.
2. Then I need to implement my method treeAggregate for the Aggregatable trait.
3. If that method implementation calls other methods such as foldLeft, then those methods must also be implemented for Aggregatable.
4. provide an implicit conversion from every type in S to Aggregatable.
5. Glue these 4 pieces together with some tricky Scala syntax which will look simple once I understand it.

[sangamon]

@crater2150

The a here is called a higher-order type parameter in the spec, as it is a type parameter of another type parameter

Thanks for the pointer. What’s still not obvious to me from this description is that a is “universally quantified” - i.e. the bound is implied for any a (including A), not just some a (unrelated to A).

[sangamon]

@jimka

If that method implementation calls other methods such as foldLeft , then those methods must also be implemented for Aggregatable .

…or in another type class, then require both in the caller’s signature: M[_] : Aggregateable : Foo.

@jimka

provide an implicit conversion from every type in S to Aggregatable .

You aren’t turning an S into an Aggregateable, you are looking up an Aggregateable that operates on instances of S. It’s more like: Provide an implicit instance of Aggregateable for every S.

@jimka

Glue these 4 pieces together with some tricky Scala syntax which will look simple once I understand it.

This has already happened in 2. and 4.

[crater2150]

@sangamon

Thanks for the pointer. What’s still not obvious to me from this description is that a is “universally quantified” - i.e. the bound is implied for any a (including A ), not just some a (unrelated to A ).

The keyword in the spec is, that this is a type constructor parameter. A type parameter with an own parameter list, that is not part of a type bound, always introduces a type constructor, which basically is a function, but on the type level.

Take the method def plus1(a: Int): Int = a + 1. It works for any a that is an int, and a is only bound, when we call the method, returning an Int. Similarly, T[a] <: TraversableOnce[a] says we have a type constructor, which takes a single parameter named a, while any type bounds behave more like the body of a function, using the variable. a is a free variable here, and only bound when we pass a type to T (which here only happens in the parameter to foldLeft, (m: T[A])).

[sangamon]

@crater2150

The keyword in the spec is, that this is a type constructor parameter. A type parameter with an own parameter list, that is not part of a type bound, always introduces a type constructor, which basically is a function, but on the type level.

Ok, thanks, this makes sense.

[jducoeur]

@jimka

I need to implement a trait (we are saying Aggregateable ) parametrized on some subset (call it S ) of the Scala types. As I understand it S is nowhere explicitly defined.

Correct, although I would describe it as “parameterized on any type for which you can come up with a sensible instance”. That is, S is entirely abstract here, and only becomes concrete in the typeclass instance.

@jimka

Then I need to implement my method treeAggregate for the Aggregatable trait.

No – treeAggregate takes an instance of Aggregateable as a parameter. That’s why I chose the awkward name Aggregateable as an example – it defines any type that can be fed into treeAggregate.

I think this is the key point of confusion. You asked how to define treeAggregate more generally, so that it could work with more types using typeclasses. That’s what I’m describing here. You define treeAggregate only once, taking an “Aggregateable” as a parameter, and then you define a typeclass instance of Aggregateable for each type you would like to be able to pass into it.

[jimka]

@jducoeur

I think this is the key point of confusion. You asked how to define treeAggregate more generally, so that it could work with more types using typeclasses. That’s what I’m describing here. You define treeAggregate only once, taking an “ Aggregateable ” as a parameter, and then you define a typeclass instance of Aggregateable for each type you would like to be able to pass into it.

Your sense that there might be some confusion is right on the money.

I saw a presentation by Martin Odersky recently where he described the type class construction as brittle, and they are fixing it in Scala 3 so fewer things can go wrong.

So for treeAggregate to work it will need the instance of Aggregatable for dispatch purpose, but it will also need the actual container (list,set,array) to actually retrieve the values from to fold over. Will treeAgregate be a method of some class/trait? which class or trait? And how does it access the container?

Will I use the syntax List(1,2,3).treeFold(0)(identity,_+_) or rather treeFold(List(1,2,3)(0)(identity,_+_) ?

[jimka]

@jducoeur @sangamon, perhaps I’m admitting defeat too early. I’ve tried to incorporate what various people have said into some coherent code. But it’s certainly not yet correct.

But I’ve copied what I hope is a minimum working example (MWE) to scastie. I’ve changed a couple of things from the discussion above. treeAggregate I’ve called treeMapReduce, and Aggregatable I’ve called TreeReducable.

If someone can suggest how to finish this implementation to work with TraversableOnce that would be incredibly kind.

I’ve also included a reference (object Reference) implementation of treeMapReduce written in the non-type-class way, plus some tests (object Testing) of how I imagine the result will be used. The tests include a commutative and a non-commutative folding function. Perhaps my idea of the final usage is wrong based on @jdcoeur’s recent comments.

[sangamon]

@jimka

If someone can suggest how to finish this implementation to work with TraversableOnce that would be incredibly kind.

What’s missing from my example above? In one single snippet:

trait Aggregateable[M[_]] {
  def foldLeft[A, B](m: M[A])(z: B)(op: (B, A) => B): B
}

implicit def traversableOnceAggregateable[T[a] <: TraversableOnce[a]]: Aggregateable[T] =
  new Aggregateable[T] {
    override def foldLeft[A, B](m: T[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
  }

def treeAggregate[M[_] : Aggregateable, A, B](objects: M[A], init: B, seqop: A => B, combop: (B, B) => B): B = {
  implicitly[Aggregateable[M]].foldLeft(objects)(???)(???)
}

treeAggregate(Seq(1, 2, 3), 0, identity[Int], (_: Int) + (_: Int))

[sangamon]

@jimka

But I’ve copied what I hope is a minimum working example (MWE) to scastie.

From a quick glance, you are still mixing up Aggregateable/Foldable (a type class providing a #foldLeft() implementation) and TreeReducable (some class/object/trait hosting a #treeMapReduce()/#treeAggregate() method that depends on #foldLeft()).

Aggregateable/Foldable is completely independent from TreeReducable - the only connection is that TreeReducable#treeMapReduce() should declare a dependency on Aggregateable/Foldable so it can work with #foldLeft() on instances of any type M that an instance of Aggregateable/Foldable exists for.

[jducoeur]

Okay, I spent a while hacking at this. Here is the compiling version of your MWE, with a lot of comments added to hopefully clarify what’s what…

[jducoeur]

@jimka

I saw a presentation by Martin Odersky recently where he described the type class construction as brittle, and they are fixing it in Scala 3 so fewer things can go wrong.

I don’t know if I’d use the word “brittle”, but it certainly involves a bunch of unintuitive boilerplate. The Scala 3 stuff should help with that (by adding new capabilities that are focused specifically on typeclasses), although I think it’s still going to take some effort to get the high concepts for the first time, if you haven’t seen them before.

[jimka]

Wow, as I said before, that’s very kind of you to work out for me. I’m excited to get the example and it seems to work. However, IntelliJ is really unhappy with it. (separate post)

I’ve started looking into the solution, and it is indeed a bit more subtle than is implied by the simplistic example shown on scalac. The solution involves 1 trait, two objects, and an implicit class (which I didn’t even know exists before today).

In curious about your thoughts in retrospect. Why is this example so much more difficult than the 10.show example from scalac, and repeatedin this medium.com blog.

Is my use case really just a bad example of something nobody would ever want to do?

Is it worth documenting and publishing this example? I’m tempted to propose it for an upcoming Paris Scala User Group presentation, once I understand it well enough to defend.

Does the example demonstrate that type classes are too complicated in Scala 2.x, so that simplifications in Scala 3 are a welcome addition?

[jimka]

As I mentioned earlier, the solution generously offered by @jducoeur seems to work, but IntelliJ doesn’t seem to like several things. Are any of these things that IntelliJ should get correctly, and I should file a bug report to JetBrains?

Warning about higher-kinded type.

Cannot resolve symbol doReduce, and also doesn’t think the imports are used—displaying them in grey italics.

Type annotation required for implicit definition.

Another higher-kinder type warning.

[sangamon]

@jimka

Warning about higher-kinded type.

Just use auto-fix to import the corresponding “advanced language feature”.

@jimka

Cannot resolve symbol doReduce , and also doesn’t think the imports are used—displaying them in grey italics.

This seems to be a bug in the presentation compiler or in the IntelliJ editor, indeed - building and executing in IntelliJ works, though.

@jimka

Type annotation required for implicit definition.

Just add the type annotation (already hinted in grey).

[sangamon]

@jimka

I’ve started looking into the solution, and it is indeed a bit more subtle than is implied by the simplistic example shown on scalac. The solution involves 1 trait, two objects, and an implicit class (which I didn’t even know exists before today).

• trait Show ~ trait TreeReducable (type class)
• object Show ~ object TreeReducable (type class instances)
• object MainShow ~ object TreeReduce (client code)

The “additional complexity” simply derives from putting another dependent API (TreeReduce) on top of TreeReducable, where the Show example directly exercises the type class in #main().

Implicit classes already have come up in this thread, and they’re also used in the Show example, for the very same purpose of adding an OO-style method invocation delegate - just that for Show, the actual type class method #show() is delegated, while in the TreeReducable case it’s the derived #treeMapReduce() method. Implicit classes are mostly a convenience construct - the same effect can be somewhat more verbosely achieved via an implicit def.

[jducoeur]

@jimka

and an implicit class (which I didn’t even know exists before today).

Yeah – implicit class is, I gather, where the “implicit” concept originally came from: it is how Scala defines extension methods. The syntax is fairly unintuitive, though, which is why Scala 3 is getting first-class extension methods to replace this.

@jimka

Is my use case really just a bad example of something nobody would ever want to do?

No, but it’s rather more complex than average, since you’re trying to build a typeclass specifically around collections. That means that everything is focused on higher-kinded types, and the syntax gets a good deal messier. (I probably spent most of an hour working it all out myself: it’s not a trivial example.)

That higher-kindedness is really why it became so much more challenging. Most typeclass examples are done with basic first-order types (or whatever the correct term is – types that aren’t type constructors), so it’s typically somewhat easier. But the underlying concepts are exactly the same with the higher-kinded typeclass: there’s just more mucking around to get the signatures to all line up correctly.

@jimka

Is it worth documenting and publishing this example? I’m tempted to propose it for an upcoming Paris Scala User Group presentation, once I understand it well enough to defend.

Makes sense to me. Folks tend to focus on the easy examples, but showing a more-sophisticated one has value.

@jimka

Does the example demonstrate that type classes are too complicated in Scala 2.x, so that simplifications in Scala 3 are a welcome addition?

Enh – I wouldn’t put too much stock in that. Keep in mind, part of why you’re finding it so hard is that the concepts are new, and the mental hurdle is significant. (Took me several years of active Scala use before I really grokked it.) The improvements to Scala 3 will help the syntax, and might slightly improve the intuition (certainly that’s a goal of Martin’s), but I still think it’s going to be non-trivial work for anyone coming from the imperative world to understand what’s going on – it’s just plain Different.

@jimka

Warning about higher-kinded type.

Ah, right – you probably need to add the higher-kinded import to clean that up. (Which I assume is what the popup is pointing you to.) There are several advanced Scala features that give warnings/errors unless you add an “I know what I’m doing” import.

@jimka

Cannot resolve symbol doReduce , and also doesn’t think the imports are used—displaying them in grey italics.

That likely is an IntelliJ weakness: in general, I’ve found IntelliJ to be weak when it comes to the combination of underscore imports and implicits. It’s actually my single biggest complaint about IntelliJ, and the main reason I’m thinking of moving to VSCode for my personal work. (Which involves a lot of that sort of stuff.) Reporting a bug can’t hurt, although I’d be really surprised if they don’t already know about it.

@jimka

Type annotation required for implicit definition.

Ah – yeah, I’m sometimes lazy about that, but it is A Very Good Idea to annotate your implicits. (And I think that will become required in Scala 3, so it’s a good habit to get into.)

[jimka]

@jimka

brittle

Yes, registering to the video by Odersky, I think I misquoted him. He didn’t say “brittle”, rather he said “heavyweight”. However, he said elsewhere in the presentation that it involves several things that makes it difficult particularly in large many-person projects where someone does it wrong, and later in the project other people suffer from the fact that their predecessors implemented things wrong.