Scala - 在递归函数中匹配传递的参数类型

Question

我有一个节点类，它可以指向另一个节点（通过next）。该节点可以分为不同的层次结构。然后，我可以在单链表中的图像中获得这些不同节点的链。然后，从该列表中的任意节点开始，我想搜索特定类型的第一个节点。因此，我为此创建了一个类型参数化函数check。但它找不到正确的匹配。下面是完整的输出代码示例，从斯卡拉底稿获得：

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]) 

的问题是：

1. 为什么会失败这样呢？它忽视了传入的类型。

2. 我该如何实现我想要的？

UPDATE：作为谏，我曾为了争夺所谓的“类型擦除”在这里，这样做手工明确的具体化使用Scala的“清单”尝试。然而，我无法在清单的帮助下进行模式匹配 - 它无法以我能想到的任何方式工作，也无法在网络上找到任何工作示例。

Answer 1

首先，我建议你向你的任务分解到：

1. 寻找具有某种特性的一个节点，并
2. 指定属性为某一类的子类。

例如，Scala集合有方法

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] 
} 

（请注意，这不是防弹：它运作良好，只有在给定的参数到部分函数是不是多态的，原因是通常我们没有可用于传递给它的参数的清单，只有它们的类型擦除类，但是因为所有的节点类都不是多态的，这不是一个问题。）

通过结合这两个函数，你应该得到想要的结果。

---

我给了Scala集合，你可以为你的情况下适应一个完整的例子：

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

以下似乎工作。不知道还有什么要说的，因为我不知道还有什么其他（也许更好）的方式来实现你想要做的。我研究了Manifest的API一段时间来想出这个。我也不知道这是否也适用于'ClassManifest'。

并照顾子类型，因为我认为这段代码将失败。

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