Beginner questions about type classes

[jimka]

@yawaramin

There is a confusion here, show is not a function at all, it is a method definition, they are different concepts in Scala. See https://stackoverflow.com/q/2529184/20371 for details

There seem to be two schools of thought in the literature I’ve read. Some people resist in calling methods functions, other authors do it freely. We are lacking a word to describe something that syntactically looks like a function, acts like a function, walks like a function, and quacks like a function. For example method, anonymous function, object with an apply method, partial function, object inheriting from Function. What should we call something that can be applied to arguments to obtain a result?

The point of my question 4 was that to me (the reader of the blog) it was confusing that one definition of show makes a function-like-entity which when called with one argument returns a String, and another show which when called with one argument returns a function-like-entity which when called returns a String, which is what the syntax def f(...)(...):String = {...} does.

[jimka]

@yawaramin

Are you familiar with Java? Let me translate the code sample you posted to Java, to give you a new perspective on it:

No, I generally try to avoid analogies to Java when possible. I’d rather try to understand the semantics rather than having to learn Java in order to understand Scala. That might indeed be an interesting endeavour, but until now is one I’ve tried to avoid.

[curoli]

A term denoting an object with an apply method? Perhaps an Applicable?

The term function has a long history.

For a long time, programming languages had two types of subroutines: procedure, that don’t return a value, and functions that do return a value.

The came C and unified procedures and functions, so now all subroutines are functions. If they don’t return a value, they have a quasi-type void that syntactically acts like a type.

Then came object-oriented languages like C++. A variable that is member of a class is a field, and a function that is a member is a method.

Now, in a purely OO language like Java, every function is a method, so we can drop the word function and only talk of methods.

Then comes Scala and resurrects the term function, but it now means something else. It is not a subroutine that returns a value, but an object of type FunctionN. Also, Scala replaces quasi-type void with Unit, which is a real type.

[jimka]

@curoli

The term function has a long history.

Sussman and Abelson (SICP) used the the word function to represent the thing you are calculating, and distinguished it from a procedure which was an algorithmic implementation. For example, the cosine function might have many different imaginable procedures to calculate its value for a given input. In Scheme some people use function to mean a procedure with no side effects.

[tarsa]

It’s best to just stick to terminology that is idiomatic in a specific language. Otherwise we wouldn’t agree on anything. Examples:

• typeclasses are denoted by keyword class in Haskell, trait in Rust, protocol in Swift, etc
• class in Scala, Java, C++, C#, etc is a classic OOP class containing both state and behaviour
• struct in C++ is almost the same thing as class in C++ - only difference is default visibility of members
• struct in C# is different from class in C# - struct is for value types, class is for reference types
• trait in Scala is not a typeclass as in Rust. trait in Scala is something in between class and interface in Java. trait in Scala can contain both state and behaviour.
• sealed class in C# is like a final class in Scala - you can’t extend them at all
• sealed class in Scala is different - it can have direct subclasses if they are defined in the same source code file
• etc

[sangamon]

@jimka

Perhaps someone can suggest a more extensive example more suitable to my problem?

I’m not sure I fully understand your problem and whether type classes (or other implicit usages) might be a part of a solution. It might help if you provided minimal, self-contained examples that highlight the structure of the problem instead of reworked extracts from your actual code base.

• Is the implementation of #treeAggregate() relevant to the problem?
• What other containers would you want to provide #treeAggregate() to, and how - via completely separate implementations? Are the three questions below related to this part at all?
• What’s ClauseAsList, BinaryOperation, etc.? Type aliases are nice if they can be looked up and if the corresponding types are used excessively - not in this kind of example.
• Just wondering: Couldn’t seqop and A be left out in exchange for an upstream #map() invocation?

@jimka

The example from scalac shows how to add a show method to Int and String . (I hesitate to say “add a method” because it doesn’t really add the method to Int nor String ; it just makes the syntax look like a method has been added).

It’s showing how to create a type class Show (that incidentally happens to have one method only) with instances for String and Int. The ShowOps wrapper is just sugar on top and not part of the type class concept as such.

@jimka

def conv(i: Int): Bdd = Bdd(i)
treeAggregate(clause, ident: Bdd, conv, (acc: Bdd, b: Bdd) => op(acc, b)) 

This could probably already be written as

treeAggregate(clause, ident, Bdd(_), op)

@jimka

1. The example starts by defining a trait Show[A] whose type parameter A represents the type of object we’d like to put on the left hand side of the .show . In my case I would like to put a container object on the left hand side. Set(1,2,3).treeAggregate(...) , List("hello","world",...).par.treeAggregate(...) etc.
2. In the example the function show does not have any type parameters. In my case I have two type parameters, [A,B] , one of which A correlates the object on the left hand side of the . to the arguments of the method.

So far this doesn’t invoke the concept of type classes.

implicit class TraversableTreeAggregate[A](val objects: TraversableOnce[A]) extends AnyVal {
  def treeAggregate[B](init: B, seqop: A => B, combop: (B, B) => B): B =
    Aux.treeAggregate(objects, init, seqop, combop)
}

@jimka

The example defines implicit vars intCanShow:Show[Int] and stringCanShow:Show[String] , i.e. having how type parameter variables, rather having fixed types Int and `String. I don’t see how to do that in my case. Do I need a combinatorial explosion of implicit variables?

This one I don’t understand.

[jimka]

@sangamon

Is the implementation of #treeAggregate() relevant to the problem?

What does the # notation mean? I see this often in scala discussions, but I’ve never understood what it means. e.g., #treeAggregate()

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

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