Observation about polynomial rings discovered when implementing in Scala

Question
1

I discovered an interesting issue when attempting to implement monoids, groups, and rings in Scala. As described in these threads (Generic matrix multiplication using typeclasses and Abstract algebra in Scala ) I used a technique based on typeclasses, even if it is unclear whether such qualifies as a typeclass, perhaps better described as a strategy pattern.

Anyway the issue is this. A ring is a set with two operators, typically called + and *. The set is a group (Abilene) with respect to + and the same set is a monoid with respect to *. So one way to implement a ring, is to first implement the additive group and the multiplicitve monoid, and then compose them by delegation. This is not a problem mathematically, but does present an interesting code partitioning problem. In particular sometimes the implementation is clearer if we implement multiplication in terms of addition. Here is an example.

The ring of polynomials: We can add and subtract mathematical polynomials. So it is easy to implement the additive group of polynomials in Scala.

We can multiply but not divide polynomials (i.e., when you divide two polynomials you might not get another polynomial), so mathematically polynomials are a monoid.

However, if I try to implement the multiplicitive monoid, I have a problem. The straightforward algorithm for multiplying polynomials such as (ax^2 + bx + c) * (fx^2 + gx + h) is to use the distributive law and compute (afx^4 + agx^3 + agx^), then (bfx^2 + bgx^2 + bhx), and finally (cfx^2 + cgx + ch). Now I have 3 polynomials that I want to add, for example with foldLeft. But wait, the multiplicitive monoid does not know how to add polynomials. To add two polynomials, I need the additive-group object. (truthfully, I don’t really need the additive-group inverse, just the add and the zero to construct the foldLeft call.)

Of course I can write an add within the curly braces of the polynomial-multiplicitive-monoid class. But them I’m duplicating code simply to satisfy the language constraints. I could also write a self contained multiply function, which has the addition operation implicitly built into it (sort of a convolution operation), but that will be more obscure. The gut feel is, I’ve already written an add function; just call it.

What is interesting is that this problem is not at all apparent mathematically, but becomes apparent when trying to code it up.

2

I found what I think is an elegant solution.
The idea is given an instance of Ring[T], I can programmatically create an instance of the multiplicitive monoid and an instance of the additive group. I can do this using the Scala new MyTrait[]{ ...} syntax, which allows me to ask the compiler to create the class for me, and just give me an instance of it at run-time.

The advantage is that I can now just implement an Ring[Int] and similarly a Field[Double] and let the underlying groups and monoids be created programmatically. And all the methods in the Ring definition can reference each other.

This makes the Polynomial issue much easier. I can Implement Ring[Polynomial[R,M]] where R is the type of coefficient, and M is the type of exponent. And then I don’t have to even think about how to isolate the additive group or multiplicitive monoid.

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

  trait Group[T] extends Monoid[T] {
    def inverse(a: T): T
  }

  trait SemiRing[T] {
    def one: T
    def zero: T
    def add(a: T, b: T): T
    def times(a: T, b: T): T
  }

  trait Ring[T] extends SemiRing[T] {
    def additiveInverse(a: T): T
    def subtract(a: T, b: T):T = add(a,additiveInverse(b))
  }

  def ringToAdditiveGroup[T](ring:Ring[T]):Group[T] = {
    new Group[T]{
      def inverse(a:T):T = ring.additiveInverse(a)
      def op(a:T,b:T):T = ring.add(a,b)
      def identity:T = ring.zero
    }
  }

  def ringToMultiplicitiveMonoid[T](ring:Ring[T]):Monoid[T] = {
    new Monoid[T]{
      def identity:T = ring.one
      def op(a:T,b:T):T = ring.times(a,b)
    }
  }

  trait Field[T] extends Ring[T] {
    def multiplicitiveInverse(a: T): T
    def divide(a: T, b: T): T = times(a, multiplicitiveInverse(b))
  }

  def fieldToMultiplicitiveGroup[T](field:Field[T]):Group[T] = {
    new Group[T]{
      def identity:T = field.one
      def op(a:T,b:T):T = field.times(a,b)
      def inverse(a:T):T = {
        require(a != field.zero,
                s"cannot compute inverse of zero of a field: ${field.zero}")
        field.multiplicitiveInverse(a)
      }
    }
  }
1 Like
3

You may want to check algebra: Algebra: Home