Beginner questions about type classes

[jducoeur]

@sangamon

I just use ‘ # ’ as a prefix to mark (class/object) members (i.e. methods and fields). Not even sure where I picked up this habit, probably someplace in the Java world.

The Type#member style is Scala type-projection syntax, so a fair number of purists like to use it to signify “member on some instance of Type”. It’s a little pedantic, but accurate. That’s likely where you picked it up.

[jducoeur]

@jimka

In my case I already have a function treeAggregate which only works for TraversableOnce and must be called as a function. I’d like to extend it to work with more types of containers, and to use the method calling syntax.

It’s a bit too early in the morning for me to really engage with this deeply, but roughly speaking:

• You should identify the functions that you require the input type to have. (I see foldLeft, not sure if you need anything else.)
• Define a typeclass – I’ll call it Aggregateable for the sake of argument – and put foldLeft (and any other functions you need to call on it) in as an abstract member.
• For each of the collection types you would like treeAggregate to be able to take, define a typeclass instance of Aggregateable. That is, for (say) List you would define Aggregateable[List], filling in the foldLeft method with one that takes a List as the first parameter and probably just forwards to List.foldLeft. More importantly, you can also define an Aggregateable[T] for any type T for which you can figure out a reasonable definition of foldLeft, regardless of whether T defines that itself.
• Adjust the signature of treeAggregate() to something like this:

  def treeAggregate[T[_]: Aggregateable, A, B](objects: T[A], init: B, seqop: A => B, combop: (B, B) => B)(implicit aggregateable: Aggregateable[T]): B = {

and use aggregateable.foldLeft(objects) instead of calling objects.foldLeft directly.

Or something like that, anyway. I’m focusing on foldLeft() because it’s what you are using here, but the nice thing about defining your own typeclass is that, if some other function would work better for your needs, you could define that as you like and use typeclass instances to implement that for each collection.

(If you do just want foldLeft, you could probably just pick up the Foldable typeclass from Cats, which IIRC already has typeclass instances for a bunch of types, and use that instead of defining your own Aggregateable.)

Hopefully that’s coherent enough to be helpful…

[jimka]

@jducoeur

Define a typeclass – I’ll call it Aggregateable for the sake of argument – and put foldLeft (and any other functions you need to call on it) in as an abstract member.

Nice clue, it is not clear to me how to define this trait with all the type parameters. Here is my obviously wrong attempt.

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

[jimka]

@jducoeur

For each of the collection types you would like treeAggregate to be able to take, define a typeclass instance of Aggregateable . That is, for (say) List you would define Aggregateable[List] , filling in the foldLeft method with one that takes a List as the first parameter and probably just forwards to List.foldLeft . More importantly, you can also define an Aggregateable[T] for any type T for which you can figure out a reasonable definition of foldLeft , regardless of whether T defines that itself.

I’m confused for two reasons

1. How do I define these instances? the example from scalac defines an instance called intCanShow of type Show[Int]. In my case I want to define an instance for every kind of List. A car cannot have a type parameter in scala so I can’t define var listIsTreeAggregable:Agregatabe[List[A]] = new Aggregatable[List[A]] { ... }
2. Do I really need to define methods for foldLeft? We can already foldLeft a List of anything. It seems to me I need to define the treeAggregate method for each of the implicit instances. Right?

[jducoeur]

@jimka

Here is my obviously wrong attempt.

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

The key thing is, in a typeclass the methods almost always take what you think of as “this” as an explicit parameter. So more like this:

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

That m parameter is the collection itself.

@jimka

How do I define these instances? the example from scalac defines an instance called intCanShow of type Show[Int]. In my case I want to define an instance for every kind of List. A car cannot have a type parameter in scala so I can’t define var listIsTreeAggregable:Agregatabe[List[A]] = new Aggregatable[List[A]] { ... }

Hmm. Well, it needs to be parameterized over A, so it has to be a def instead of a val (since vals can’t have type parameters). So something like:

def listAsTreeAggregateable[A]: Aggregateable[List[A]] = new Aggregateable[List[A]] { ... }

@jimka

Do I really need to define methods for foldLeft ? We can already foldLeft a List of anything.

Yeah, but that’s irrelevant. Remember, a typeclass is a whole separate wrapper around types. What methods the types themselves implement doesn’t have much to do with that typeclass’ definition, although it sometimes means that the typeclass instance for a particular type might be a one-line forwarder.

@jimka

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. The Aggregateable is a parameter to treeAggregate in this design.

[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?