Find out if two variables inherit from the same parameterized type in Scala

Question

here is my Problem:

I try to aggregate a List of Objects:

val list = List(Foo(1), Foo(2), Bar(2), Bar(3), Baz(5), Baz(3))

After the aggregation i want to have only one object for every aggregatable type in this list. In this Example Foo and Bar should be aggregatable where Baz isn't, so the result should be:

List(Foo(3), Bar(5), Baz(5), Baz(3))

My Idea was to define a trait Aggregatable as follows:

trait Aggregatable[T] {
    def aggregate(agg: T): T
}

case class Foo(val x: Int) extends Aggregatable[Foo] {
    def aggregate(agg: Foo) = {
        val x = (0 /: List(this, agg))((old, elem) => (old + elem.x))
        new Foo(x)
    }
}

case class Bar(val x: Int) extends Aggregatable[Bar] {
    def aggregate(agg: Bar) = {
        val x = (0 /: List(this, agg))((old, elem) => (old + elem.x))
        new Bar(x)
    }   
}

case class Baz(val x: Int)

Well, I think this is the obvious part of the Problem...

In the next step I try to aggregate the list. First I group the list into lists of homogenious types:

val grouped = list.groupBy( _.getClass().toString() )

/* => grouped should be
 * Map(
 *     class Foo -> 
 *         List(Foo(1), Foo(2)),
 *     class Bar -> 
 *         List(Bar(3), Bar(4)), 
 *     class Baz -> 
 *         List(Baz(5), Baz(3))
 * )
 */

Now for the sake of simplicity lets now assume that we want to find out if the first two elements of the first list are aggregatable:

val firstList = grouped.toList.apply(0)._2 // List(Foo(1), Foo(2))
val a = firstList (0) // Foo(1)
val b = firstList (1) // Foo(2)

This is where my actual problem begins. To determine if a and b can be aggregated, there must be a way to ask if a and b inherit from the same type Aggregatable[T] for some fixed T.

My way to ask this was to define a type aggregatablePair:

type aggregatablePair = Pair[T, T] forSome { type T <: Aggregatable[T] }

Build a pair out of a and b:

val pair = (a, b)

and aggregate them if they are an aggregatablePair:

pair match {
    case aggPair: aggregatablePair => aggPair._1.aggregate(aggPair._2)
    case _ => println("pair is not aggregatable")
}

but this doesn't work... the error is:

type mismatch; 
found: aggPair._2.type (with underlying type T forSome { type T <: Aggregatable[T] })
required: T where type T <: Aggregatable[T]

In my opinion it sounds like the found type matches the required type... can anyone tell me why it dosn't? And what would be the right way to express what I want?

thank you for any help

Answer 1

I've found a quite "satisfying" solution to my problem. The general Idea is to add a method aggregateOrCons with result type List[Any] to the Aggregatable trait, which either aggregates two Objects if they are from the same type or returns a list containing the input arguments.

trait Aggregatable[T] {
    def aggregate(agg: T): T

    def aggregateOrCons(agg: Any): List[Any] = {
        agg match {
            case t: T => List(this.aggregate(t))
            case a => List(a, this)
        }
    }
}

My input parameters are now being sorted instead of grouped by their class, because I only need to ensure that objects of the same type appear in a row.

val list = List(new Foo(1), new Baz(1), new Baz(2), new Bar(3), new Foo(2), new Bar(4))
val sorted = list.sortWith(
    (a1, a2) => (a1.getClass().toString() compareTo a2.getClass().toString()) < 0
)

In the next step I define a method to aggregate two objects of type Any. If both input arguments are of type Aggregatable, I apply the aggregatableOrCons method on them (which will result either the aggregation of the two arguments, if they are equal, or a list containing the arguments if they are not). If one of them is no Aggregatable a list containing the input arguments will be returned.

def aggregate(a: Any, b: Any): List[Any] = a match {
    case agg1: Aggregatable[_] => b match {
        case agg2: Aggregatable[_] => agg1.aggregateOrCons(agg2)
        case b => List(b, agg1)
    }
    case a => List(b, a)
}

Now the only requirement left to be able to fold the list of sorted input artuments is a neutral element. It should aggregate with anything and should just return the input argument.

object NeutralAggregatable extends Aggregatable[Any] {
    def aggregate(agg: Any) = agg
}

Now I can fold the sorted list

val neutral: Any = NeutralAggregatable
val aggregated = (List(neutral) /: sorted)((old, elem) => 
    (aggregate(old.head, elem) ::: old.tail)
)

println(aggregated) // List(Foo(3), Baz(2), Baz(1), Bar(7))

Answer 2

A type parameter T can't be determined at runtime, due to the type erasure of the JVM. But you don't need to (and you know what T is because it is also the class from getClass keys in the map, but you don't need to know).

Since you know that a and b are the same type (e.g. Foo), then if a.instanceOf[Aggregatable] (or a.instanceOf[Aggregatable[_]]), then b.instanceOf[Aggregatable] is too. So just test the first item of the list and if true, accumulate all elements.

---

P.S. I would have used a category theory collection library, that has a Monoid type, rather than reinventing it as Aggregatable. Monoid knows how to accumulate itself. See page 7 of Applicative programming with effects.

Conceptually you are doing the following functional programming steps.

1. Fold over the list creating a collection (e.g. list or map) of lists, collating items of the same type in distinct lists. Use elem.getClass to test for distinctness.
2. Map the collection of lists, folding each sub-list to accumulate.

I see you accomplished #1 with groupBy.