Scala - match a passed parameter against a passed type parameter in a recursive function

Question

I have a node class, which can point to another node (via next). That node can be subclassed in different hierarchies. Then, I can have a chain of these various nodes, in an image of a single-linked list. And then, starting from an arbitrary node in that list, I want to search for the first one of a specific type. Therefore, I create a type-parametrized function check for that matter. But it fails in finding the correct match. Here is the complete with output code example, taken from Scala Worksheet:

class A (i: Int) {
    var next: Option[A] = None
    def + (a: A) = {
      next = Some(a)
      a
    }
    override def toString = super.toString + "[" + i + "]"
}
class B (i: Int) extends A (i)
class C (i: Int) extends B (i)
class D (i: Int) extends B (i)

object test {

    val start = (new A(0))                    //> start  : A = A@e80a59[0]
    val test = start + (new A(1)) + (new B(2)) + (new C(3)) + (new D(4)) + (new A(5)) + (new C(6))
                                                  //> test  : A = C@5d173[6]

    def check[T <: B](a: A): Option[B] = {
        println("starting search for " + a)
        a match {
          case t: T =>
            println("SUCCESS, found=" + t)
            Some(t)
          case wrong =>
            println("did not find! wrong=" + wrong)
            a.next match {
            case Some(nxt) =>
                println("checking next=" + nxt)
                check[T](nxt)
            case _ =>
                println("SEARCH FAILED")
                None
          }
        }
    }                                         //> check: [T <: B](a: A)Option[B]

    /* correct - i expect this */
    println(check[C](new A(1)))               //> starting search for A@1f9dc36[1]
                                                  //| did not find! wrong=A@1f9dc36[1]
                                                  //| SEARCH FAILED
                                                  //| None
    /* correct - i expect this */
    println(check[D](new A(2)))               //> starting search for A@e86da0[2]
                                                  //| did not find! wrong=A@e86da0[2]
                                                  //| SEARCH FAILED
                                                  //| None
    /* incorrect - it must fail looking for C */
    println(check[C](new B(4)))               //> starting search for B@1754ad2[4]
                                                  //| SUCCESS, found=B@1754ad2[4]
                                                  //| Some(B@1754ad2[4])
    println(check[B](start))                  //> starting search for A@e80a59[0]
                                                  //| did not find! wrong=A@e80a59[0]
                                                  //| checking next=A@fe64b9[1]
                                                  //| starting search for A@fe64b9[1]
                                                  //| did not find! wrong=A@fe64b9[1]
                                                  //| checking next=B@186db54[2]
                                                  //| starting search for B@186db54[2]
                                                  //| SUCCESS, found=B@186db54[2]
                                                  //| Some(B@186db54[2])
    /* incorrect - it must find C(3) instead */
    println(check[C](start))                  //> starting search for A@e80a59[0]
                                                  //| did not find! wrong=A@e80a59[0]
                                                  //| checking next=A@fe64b9[1]
                                                  //| starting search for A@fe64b9[1]
                                                  //| did not find! wrong=A@fe64b9[1]
                                                  //| checking next=B@186db54[2]
                                                  //| starting search for B@186db54[2]
                                                  //| SUCCESS, found=B@186db54[2]
                                                  //| Some(B@186db54[2])
    /* incorrect - it must find D(4) instead */
    println(check[D](start))                  //> starting search for A@e80a59[0]
                                                  //| did not find! wrong=A@e80a59[0]
                                                  //| checking next=A@fe64b9[1]
                                                  //| starting search for A@fe64b9[1]
                                                  //| did not find! wrong=A@fe64b9[1]
                                                  //| checking next=B@186db54[2]
                                                  //| starting search for B@186db54[2]
                                                  //| SUCCESS, found=B@186db54[2]
                                                  //| Some(B@186db54[2])

The questions are:

1. Why does it fail like that? It disregards the passed type.

2. How can I acheive what I want?

UPDATE: As adviced, I have tried using a Scala "manifest" in order to battle what is called "type erasure" here, by doing this manual explicit reification. However, I am not able to make the pattern matching with the help of the manifest - it simply does not work with it in any way that I can think of, nor I was able to find any working example on the net.

Answer 1

First, I'd suggest you to split your task to:

1. searching for a node having a certain property, and
2. specifying the property to be a subclass of certain class.

For example, Scala collections have method

def collectFirst[B](pf: PartialFunction[A, B]): Option[B]

that finds the first element for which the function is defined and applies the function to it. In your case, you'd use partial functions on nodes instead on their elements.

Then, you could create a function that creates such a partial function given (an implicit) manifest:

def subclass[A <: AnyRef](implicit m: Manifest[A]): PartialFunction[Any,A] = {
  // Works properly only for arguments that have non-polymorphic types!
  case x if m.erasure.isInstance(x)  => x.asInstanceOf[A]
}

(Note that this isn't bullet-proof: It works well only if the arguments given to the partial function are not polymorphic. The reason is that in general we don't have manifests available for the arguments that are passed to it, only their type-erased classes. But since all your node classes aren't polymorphic, this shouldn't be an issue.)

By combining these two functions, you should get the desired result.

---

I'll give a complete example for Scala collections which you can adapt for your case:

import scala.reflect._

object Test extends App {
  // Scala collections have this method:
  // def collectFirst[B](pf: PartialFunction[A, B]): Option[B]

  def subclass[A <: AnyRef](implicit m: Manifest[A]): PartialFunction[Any,A] = {
    // Works properly only for arguments that have non-polymorphic types!
    case x if m.erasure.isInstance(x)  => x.asInstanceOf[A]
  }

  def collectFirst[T <: AnyRef](xs: Seq[AnyRef])(implicit m: Manifest[T]) =
    xs.collectFirst(subclass[T]);

  val s: Seq[AnyRef] = Seq(
    new java.lang.Object(),
    "a",
    3 : java.lang.Integer,
    '@' : java.lang.Character
  );

  println(collectFirst[String](s));
  println(collectFirst[AnyRef](s));
  println(collectFirst[java.lang.Character](s));
  println(collectFirst[java.lang.Integer](s));
}

Answer 2

The following seems to work. Don't know what else to say about it, since I don't know what other (and probably better) ways there are to achieve what you want to do. I studied the API of Manifest for a while to come up with this. Also I don't know if this works with 'ClassManifest', too.

And take care of subtyping, since I suppose this code will fail then.

scala> trait A
defined trait A        
scala> case class A1() extends A
defined class A1    
scala> case class A2() extends A
defined class A2

scala> def check[T <: A](a: A)(implicit m: Manifest[T]) = a.getClass == m.erasure
check: [T <: A](a: A)(implicit m: Manifest[T])Boolean

scala> check[A1](A2())
res7: Boolean = false
scala> check[A2](A2())
res8: Boolean = true