Generic matrix multiplication using typeclasses

TLDR; I’ve implemented, on scastie, a pedagogical math function fast-exponent, to help me understand typeclasses. I have completely avoided implicits. QUESITON: how would I refactor this code to use implicits? Or better: should I use implicits?

I’m trying to understand some aspects of typeclasses. There is an object model to understand which I think is easy to neglect once you understand. Rather than all the methods being in one class, we have methods coming from several different classes.

There are two objects in play. One is the sort of model object which contains code (variables, functions, methods) which characterize a class of objects, and separate from that, there’s the object being manipulated.

For example, there is the pair of integers, 3, and 7, which we’d like to add, and separate from that there is an object which represents the monoid of integers inasmuch as it contains/encapsulates the identity-element and plus operation of the monoid.

I’m trying to understand how this whole thing works.

I have implemented a scastie solution monoid fast exponent to the following pedagogical problem.

I think the question of implicit variable obscures the idea. So I’ve written the scastie example avoiding implicit variables altogether.

HERE IS the mathematics problem I’d like to solve for pedagogical reasons.
The code works but I don’t understand how to refactor the code to use implicits.

In any monoid (in any mathematical monoid) I can compute an element raised to an integer power in log(n) operations with the following power function. For example a String repeated n times or a Double raised to the n power. The power function needs to know the identity of the monoid and also the operation, but doesn’t care if that operation is string concatenation, or addition or multiplication or whatever.

  def power[T](m:T, n:Int, monoid:Monoid[T]):T = {
    if (n == 0)
      monoid.identity
    else if (n == 1)
      m
    else if (n % 2 == 0) {
      val m2 = power(m, n / 2, monoid)
      monoid.op(m2, m2)
      }
      else
        monoid.op(m, power(m, n - 1, monoid))
  }

  trait Monoid[T] {
    def op(a:T,b:T):T
    var identity:T
  }

I want to make this work for some exotic monoids:
For example,

  1. The monoid of matrices containing Double entries.
  2. The monoid of matrices containing Integer entries, but where integer addition and multiplication is modulo 5.
  3. The monoid of 2x2 matrices with 3x3 matrices as entries, and these 3x3 matrices contain Double entries.
  4. The monoid of 2x2 matrices with 3x3 matrices as entries, and these 3x3 matrices contain Integer entries which use modulo 5, 7, and 11 multiplication.

Naive take.

So if I understand your suggestion, you’ve added an implicit argument to the power function. But this doesn’t really buy much, right? or did I misunderstand the generalization. For example the loop at the bottom cannot benefit from the implicit argument. Because the value of the implicit argument cannot be determined by type alone, in fact it depends on k. Right?

  for {
    k <- Seq(5, 7, 11)
    matrixMonoid = SquareMatrixMultiplicationMonoid(2, MatrixRing(3, Zmod(k)))
  } println(power(Matrix(2, Seq(Seq(m1, m2), Seq(m3, m4))), 50)(matrixMonoid))

It may not seem to buy much in this specific scenario. In general, there’s many types that do have one dedicated natural monoid that can be declared in the type’s companion object and then will be in scope wherever needed from there on. And in other real world examples, the monoid may be required multiple times in a broader scope. In these cases you’ll only have to declare your chosen monoid instance for the given type once for the whole scope.

Furthermore, type classes tend to evolve into a Lego style ecosystem where (implicit or explicit) instances of one type class can (entirely or with additional arguments) be derived from implicit instances of another type class. Quick example, using context bounds (e.g. [T : Monoid]) instead of implicit parameter lists and the better-monadic-for plugin for implicit declarations within for expressions.

1 Like

what is implicit0 which you’ve used in the for comprehension?

@jimka so the main problem with your approach right now, is that many people debates if Monoid and friends should be considered a typeclass or not. This is discussed because there are multiple valid implementations of those for the traditional numeric types.

The approach that cats took was to make it a typeclass nevertheless, provide the “default” (most common) instance and then, on a separate project, add a couple of newtypes to be able to provide different instances.

The other problem with your code is that you are looking at your instances as data, by making the case classes and asking for parameters like dimension

So yeah, your example is really not a good one to learn / teach typeclasses.

1 Like

What is the problem with looking at instances as data? They are data. Right? For example the ring of integers modulo p really does depend on the integer p, right? And the ring of square matrices really does depend on the dimension.

I took a look at the documentation for spire. But didn’t dig deep. I noticed there is an implementation for polynomial which supports any semi-ring as coefficients. However, it limits exponents only to integers. Whereas the exponents also need to be a monoid to work in a most general way. I.e., to multiply two polynomials you need to be able to add exponents. And the identity (additive and multiplicitive) polynomial has exponent which is the identity for the group.

BTW spire does seem to be very interesting in terms of examples.

It’s not a problem as such, but the classical “pure” scenario for a type A and an abstraction F[_] is that A has-a F[A], i.e. there is one instance of F for A, implemented as a type class instance, completely independent of the value level. For the monoid abstraction, this holds for some types (e.g. String, List[_]), but once you enter the numeric domain, there may be different choices at the type level (e.g. addition vs. multiplication) or even dependencies to the value level, as in your dimension example.

Well it is hard for me to generalize something I don’t understand. I’m trying to implement a problem which I’ve not been able to do for several years now, using Scala. I.e., a fast-exponent function which works on any monoid.

For me it seems like a good example particularly because it solves the problem pretty elegantly. BTW it does underscore my point that typeclasses and implicits are two different things but which Scala conflates, making it more difficult to understand. To self criticize, this evidence might only be confirmation bias, it is evidence which supports my idea. But I admit, my experience is limited.

That the whole point of a typeclass si to separate behaviour from data.

Sure, as everything is just 1 & 0
But, in the conceptual level, a typeclass is not data, is behavior; but your instances are data and require data.
For example, your Monoid for Matrix requires to know the dimension of the Matrix it works for, which means that there will never be a single monoid for Matrix

Again, I am not saying that you are doing something good or bad, I am just saying that your code is not a good example of typeclasses. This, in turn, may be a good argument to say that Monoid should not be modeled like that; I am not totally sure since I didn’t think too much about your code, to be honest, but it seems you shouldn’t need that dimension property.
Of course, another stake at this is that a Matrix should encode its dimensions at the type level so there would be different instances of Monoid for every dimension… but yeah, that is way too much.

1 Like

Did you read the conversation that we had with Fabio yesterday about this? The TL;DR; is that implicitly nature of the instances is core to what a typeclass is.

1 Like

yes, right, a ring needs to have-a additive group and a multiplicitive monoid. Whereas a field needs to have an additive group, a multiplicitive monoid, and a multiplicitive group (of non-zero elements). So by traditional OO design, a ring cannot inherit from monoid and from group in two different ways.

In mathematics we say that a field IS AN additive group and its set of non-zero elements IS A multiplicitive group. But this mathematical-IS-A does not translate to a Scala-OO-IS-A.

no, where is this conversation? Is it lost on discord? I find discord a poor tool for archiving conversations.

Well at the moment, I don’t agree. It seems to me that implicits are a syntactical nicity, but offer no expressive power. I can always call implicitly[XYZZY] rather than relying on the compiler to do it for me.

Again, my opinion comes with a grain of salt, as I’m just learning.

To expand on @BalmungSan’ s point… A type class is (surprise!) a type level construct. Strictly speaking, if you need anything besides the pure type to “select” an instance, it’s not really a type class.

In Haskell, the addition/multiplication monoid dichotomy would not be resolved through something like implicit scoping, but by using wrapper types Sum and Product for the underlying type, e.g. Int, each having a dedicated, unique Monoid instance. (This could be done in Scala, as well, but, especially since wrapper types usually come with some overhead/cost, it’s often more convenient to (ab?)use implicit scoping.) For the dimension problem, one would have to venture into dependent typing, “lifting” the dimension from value to type level.

1 Like

The important difference is, that an implicit has to be unambiguous, i.e. for a given A there can be only one implicit F[A] in scope, otherwise it will not be resolved implicitly. This matches typeclass coherence (as e.g. enforced in Haskell).

If your F[A] is ambiguous, I’d rather call this a use of the strategy pattern rather than a typeclass.

To model mathematical monoids as typeclasses correctly, there should probably a distinction between additive and multiplicative monoids. For the matrix types their size and content would have to be encoded in their type. Same goes for the integers. If you view types as mathematical sets, the integers modulo 5 are a different set than the set of integers, so they should have a different type

1 Like

So you’re saying that a typeclass is just a special case of a strategy pattern in which there is only one possible instance?

no, where is this conversation?

Here: Discord

It seems you may want to tune your notifications, I guess you also didn’t check all this that I answered to you yesterday about an unrelated topic: Discord & Discord


No, a typeclass is a way to get a value / behaviour given a type.
For example, Functor[List] is un ambiguous and you usually don’t even need to look at the implementation because you expect what it will do.
But, again, Monoid is probably not a good example; at least not how it has been traditionally modeled.

The Scala language is not capable of representing certain mathematical types as Scala types. That’s not a surprise.

BTW I don’t think it makes sense to say that one set of the integers 0 to 4 is different than another set of integers 0 to 4.

Scala is also not able (as far as I know) to distinguish different types of integer. It would be really nice if I could distinguish the Integer type of array index from the integers which are used as values within the matrix. That would indeed be useful from time to time.

Well, you certainly can do that.
That is what the newtypes approach that I mentioned before does.