Implementing a generic accumulator in Scala

Question
1

I have the following implementation of an accumulator in Scala.

package net
package projecteuler
package utils
package accumulators

import scala.math.Ordered

final class Max (private var m : Long) {
  def apply(x : Long) {
    if (x > m) {
      m = x
    }
  }

  def result : Long = {
    m
  }
}

I want to make this implementation generic, so that it works with all ordered types. Specifically, Int, Long and String.

So I tried this:

package net
package projecteuler
package utils
package accumulators

import scala.math.Ordered

final class Max[T <: Ordered[T]] (private var m : T) {
  def apply(x : T) {
    if (x > m) {
      m = x
    }
  }

  def result : T = {
    m
  }
}

The above code compiles, but fails with the following message when I try to create a Max[Long].

$ scala
Welcome to Scala 2.12.8 (OpenJDK 64-Bit Server VM, Java 11.0.2).
Type in expressions for evaluation. Or try :help.

scala> import net.projecteuler.utils.accumulators.Max
import net.projecteuler.utils.accumulators.Max

scala> val m = new Max[Long](0L)
<console>:12: error: type arguments [Long] do not conform to class Max's type parameter bounds [T <: scala.math.Ordered[T]]
   val m = new Max[Long](0L)
       ^
<console>:12: error: type arguments [Long] do not conform to class Max's type parameter bounds [T <: scala.math.Ordered[T]]
   val m = new Max[Long](0L)

Where am I going wrong? Why is Long not an Ordered? How do I get the accumulator to work with Long’s.

2

You’ll probably want to use Ordering instead of Ordered.

final class Max[T: Ordering](private var m: T) {
  import Ordering.Implicits._

  def apply(x: T) {
    if (x > m) {
      m = x
    }
  }

  def result: T = {
    m
  }
}

This code says that T needs to have an Ordering. The reason that some types have an Ordering but are not Ordered is that you can’t make an existing class extend another class or trait without changing its definition (which might be out of your control), but you can still define an Ordering for it.

Also, you can call new Max(0L) and Scala will infer the type parameter for you.

1 Like
3

I have three comments. First is on your code:

Long doesn’t extend OrderedLong, though RichLong does. There is an implicit conversion from Long to RichLong automatically available. val m = new Max(0L) should work, and give you a Max[RichLong]

Second is what your code should better be, but Jasper already answered that.

Third is your general class of accumulators. They’re a kind of mathematical object that’s well known and well studied. It’s called a semigroup, and is useful in many situations. Most FP libraries will have one of those, with all the trimmings, available for you, so that you don’t have to fully re-invent the wheel, and take advantage of others who also studied the same problem.You can find more information here: https://typelevel.org/cats/typeclasses/semigroup.html

4

I actually found out in a book “Scala for the impatient” that doing “class Max[T <% Ordered[T]]” works. We have to use a so-called “view-bound”.

5

Don’t do that. That’s deprecated for good reasons (and removed in 2.13 I think?)

If you must, use the equivalent class Max[T](t: T)(implicit view T => Ordered[T])

6

Thanks for the suggestion, I now have the following working code:

package net
package projecteuler
package utils
package accumulators

import scala.math.Ordered

final class Max[T] (private var m : T) (implicit view : (T => Ordered[T])) {
  def apply(x : T) {
    if (view(x) > m) {
      m = x
    }
  }

  def result : T = {
    m
  }
}
7

Here are few ways to achieve the same thing:

  // WARNING: view bounds are deprecated
  final class OrderedMaxImplicitViews[T <% Ordered[T]](private var m: T) {
    def apply(x: T): Unit = {
      if (x > m) {
        m = x
      }
    }

    def result: T = m
  }
  new OrderedMaxImplicitViews(5)
  new OrderedMaxImplicitViews(BigInt(5))

  final class OrderedMaxSubType[T <: Ordered[T]](private var m: T) {
    def apply(x: T): Unit = {
      if (x > m) {
        m = x
      }
    }

    def result: T = m
  }
//  new OrderedMaxSubType(5) // Int is not a subtype of Ordered[Int]
  new OrderedMaxSubType(BigInt(5))

  final class OrderingMaxContextBound[T: Ordering](private var m: T) {
    def alternativeApply1(x: T): Unit =
      m = Ordering[T].max(m, x)
    
    def alternativeApply2(x: T): Unit = {
      if (Ordering[T].gt(x, m)) {
        m = x
      }
    }
    
    private val ordering = Ordering[T]
    import ordering.mkOrderingOps

    def apply(x: T): Unit = {
      if (x > m) {
        m = x
      }
    }

    def result: T = m
  }
  new OrderingMaxContextBound(5)
  new OrderingMaxContextBound(BigInt(5))

  final class OrderingMaxImplicit[T](private var m: T)(
      implicit ordering: Ordering[T]) {
    import ordering.mkOrderingOps

    def apply(x: T): Unit = {
      if (x > m) {
        m = x
      }
    }

    def result: T = m
  }
  new OrderingMaxImplicit(5)
  new OrderingMaxImplicit(BigInt(5))

OrderingMaxContextBound is the preferred approach because it works for all numeric types and has compact class signature (only T: Ordering vs T + (implicit ordering: Ordering[T]))

I’ve included alternative apply methods, so you can choose one which you prefer. mkOrderingOps does implicit conversions, so it could impose some performance hit.

8

Thanks for the detailed response. Now I have seen different ways of achieving the same goal. Ideally I would have been happy if “final class Max[T <: Ordered[T]] …” would have worked for Int, Long and String, but now I know how to explicitly get the desired result using an implicit parameter. I like the fact that the implicit conversion is explicitly stated in the class header.