Scala: generic weighted average function

Question

I want to implement a generic weighted average function which relaxes the requirement on the values and the weights being of the same type. ie, I want to support sequences of say: (value:Float,weight:Int) and (value:Int,weight:Float) arguments and not just: (value:Int,weight:Int). [See my earlier question in the run up to this.]

This is what I currently have:

def weightedSum[A: Numeric](weightedValues: GenSeq[(A, A)]): (A, A)

def weightedAverage[A: Numeric](weightedValues: GenSeq[(A, A)]): A = {
    val (weightSum, weightedValueSum) = weightedSum(weightedValues)
    implicitly[Numeric[A]] match {
        case num: Fractional[A] => ...
        case num: Integral[A] => ...
        case _ => sys.error("Undivisable numeric!")
    }
}

This works perfectly if I feed it for example:

val values:Seq[(Float,Float)] = List((1,2f),(1,3f))
val avg= weightedAverage(values)

However if I don't "upcast" the weights from Int to Float:

val values= List((1,2f),(1,3f)) //scalac sees it as Seq[(Int,Float)] 
val avg= weightedAverage(values)

Scala compiler will tell me:

error: could not find implicit value for evidence parameter of type Numeric[AnyVal]
val avg= weightedAverage(values)

Is there a way of getting round this?

I had an attempt at writing a NumericCombine class that I parameterized with A and B which "combines" the types into a "common" type AB (for example, combining Float and Int gives you Float) :

abstract class NumericCombine[A: Numeric, B: Numeric] {
    type AB <: AnyVal

    def fromA(x: A): AB
    def fromB(y: B): AB
    val num: Numeric[AB]

    def plus(x: A, y: B): AB = num.plus(fromA(x), fromB(y))
    def minus(x: A, y: B): AB = num.minus(fromA(x), fromB(y))
    def times(x: A, y: B): AB = num.times(fromA(x), fromB(y))
}

and I managed to write simple times and plus functions based on this with the typeclass pattern, but since NumericCombine introduces a path-dependent type AB, "composing" the types is proving to be more difficult than I expected. look at this question for more information and see here for the full implementation of NumericCombine.

Update

A somewhat satisfactory solution has been obtained as an answer to another question (full working demo here) however there is still room for some design improvement taking into account the points raised in the discussion with @ziggystar.

Answer 1

Linear combinations

I think the more general task that involves weighing/scaling some elements of type T by a scalar of type S is that of a linear combination. Here are the constraints on the weights for some tasks:

• linear combination: no constraints
• affine combination: weights sum to one
• canonical combination/weighted average: weights are non-negative
• convex combination: weights sum to one and are non-negative

So the most general case according to this classification is the linear combination. According to Wikipedia, it requires the weights, S, to be a field, and T to form a vector space over S.

Edit: The truly most general requirement you can have on the types is that T forms a module (wiki) over the ring S, or T being an S-module.

Spire

You could set up these requirements with typeclasses. There's also spire, which already has typeclasses for Field and VectorSpace. I have never used it myself, so you have to check it out yourself.

Float/Int won't work

What is also apparent from this discussion, and what you have already observed, is the fact that having Float as a weight, and Int as the element type will not work out, as the whole numbers do not form a vector space over the reals. You'd have to promote Int to Float first.

Promotion via typeclass

There are only two major candidates for the scalar type, i.e., Float and Double. And mainly only Int is a candidate for promoting, so you could do the following as a simple and not so general solution:

case class Promotable[R,T](promote: R => T)

object Promotable {
  implicit val intToFloat = Promotable[Int,Float](_.toFloat)
  implicit val floatToDouble = Promotable[Float,Double](_.toDouble)
  implicit val intToDouble = Promotable[Int,Double](_.toDouble)

  implicit def identityInst[A] = Promotable[A,A](identity)
}As a "small" solution you could write a typeclass 

def weightedAverage[S,VS](values: Seq[(S,VS)])(implicit p: Promotable[VS,S]) = ???