How to define a function as generic across all numbers in scala?

Question

I thought I needed to parameterise my function across all Ordering[_] types. But that doesn't work.

How can I make the following function work for all types that support the required mathematical operations, and how could I have found that out by myself?

  /**
   * Given a list of positive values and a candidate value, round the candidate value
   * to the nearest value in the list of buckets.
   *
   * @param buckets
   * @param candidate
   * @return
   */
  def bucketise(buckets: Seq[Int], candidate: Int): Int = {

    // x <= y
    buckets.foldLeft(buckets.head) { (x, y) =>
      val midPoint = (x + y) / 2f

      if (candidate < midPoint) x else y
    }
  }

I tried command clicking on the mathematical operators (/, +) in intellij, but just got a notice Sc synthetic function.

Answer 1

If you want to use just the scala standard library, look at Numeric[T]. In your case, since you want to do a non-integer division, you would have to use the Fractional[T] subclass of Numeric.

Here is how the code would look using scala standard library typeclasses. Note that Fractional extends from Ordered. This is convenient in this case, but it is also not mathematically generic. E.g. you can't define a Fractional[T] for Complex because it is not ordered.

def bucketiseScala[T: Fractional](buckets: Seq[T], candidate: T): T = {
  // so we can use integral operators such as + and /
  import Fractional.Implicits._
  // so we can use ordering operators such as <. We do have a Ordering[T] 
  // typeclass instance because Fractional extends Ordered
  import Ordering.Implicits._
  // integral does not provide a simple way to create an integral from an 
  // integer, so this ugly hack
  val two = (implicitly[Fractional[T]].one + implicitly[Fractional[T]].one)
  buckets.foldLeft(buckets.head) { (x, y) =>
    val midPoint = (x + y) / two
    if (candidate < midPoint) x else y
  }
}

However, for serious generic numerical computations I would suggest taking a look at spire. It provides a much more elaborate hierarchy of numerical typeclasses. Spire typeclasses are also specialized and therefore often as fast as working directly with primitives.

Here is how to use example would look using spire:

// imports all operator syntax as well as standard typeclass instances
import spire.implicits._
// we need to provide Order explicitly, since not all fields have an order. 
// E.g. you can define a Field[Complex] even though complex numbers do not 
// have an order.
def bucketiseSpire[T: Field: Order](buckets: Seq[T], candidate: T): T = {
  // spire provides a way to get the typeclass instance using the type 
  // (standard practice in all libraries that use typeclasses extensively)
  // the line below is equivalent to implicitly[Field[T]].fromInt(2)
  // it also provides a simple way to convert from an integer
  // operators are all enabled using the spire.implicits._ import
  val two = Field[T].fromInt(2)
  buckets.foldLeft(buckets.head) { (x, y) =>
    val midPoint = (x + y) / two
    if (candidate < midPoint) x else y
  }
}

Spire even provides automatic conversion from integers to T if there exists a Field[T], so you could even write the example like this (almost identical to the non-generic version). However, I think the example above is easier to understand.

// this is how it would look when using all advanced features of spire
def bucketiseSpireShort[T: Field: Order](buckets: Seq[T], candidate: T): T = {
  buckets.foldLeft(buckets.head) { (x, y) =>
    val midPoint = (x + y) / 2
    if (candidate < midPoint) x else y
  }
}

Update: spire is very powerful and generic, but can also be somewhat confusing to a beginner. Especially when things don't work. Here is an excellent blog post explaining the basic approach and some of the issues.