scala - 返回与传递函数相同的类型

Question

我有以下广度优先搜索的代码实现。

trait State{
   def successors:Seq[State]
   def isSuccess:Boolean = false
   def admissableHeuristic:Double
}
def breadthFirstSearch(initial:State):Option[List[State]] = {
   val open= new scala.collection.mutable.Queue[List[State]]
   val closed = new scala.collection.mutable.HashSet[State]
   open.enqueue(initial::Nil)
   while (!open.isEmpty){
      val path:List[State]=open.dequeue()
      if(path.head.isSuccess) return Some(path.reverse)
      closed += path.head
      for (x <- path.head.successors)
        if (!closed.contains(x))
          open.enqueue(x::path)
   }

   return None
}

如果我为我的特定问题定义 State 的子类型

class CannibalsState extends State {
 //...
}

让 breadthFirstSearch 返回与传递的子类型相同的子类型的最佳方法是什么？

假设我对此进行了更改，以便针对我的特定问题有 3 个不同的状态类，并且它们共享一个共同的父类(super class)型:

abstract class CannibalsState extends State {
 //...
}
class LeftSideOfRiver extends CannibalsState {
 //...
}
class InTransit extends CannibalsState {
 //...
}
class RightSideOfRiver extends CannibalsState {
 //...
}

如何使类型有效，以便在传递 LeftSideOfRiver 实例时，breadthFirstSearch 推断出正确的返回类型是 CannibalsState ？

这可以通过抽象类型成员来完成，还是必须通过泛型来完成？

Answer 1

一种选择是使用 Randall 描述的泛型。如果您想使用抽象类型成员实现类似的功能，那么您可以这样做(基于 Mitch 的代码):

trait ProblemType {

    type S <: State

    trait State {
        def successors: Seq[S]
        def isSuccess: Boolean = false
        def admissableHeuristic: Double
    }

    def breadthFirstSearch(initial: S): Option[List[S]] = {
        val open = new scala.collection.mutable.Queue[List[S]]
        val closed = new scala.collection.mutable.HashSet[S]
        open.enqueue(initial :: Nil)
        while (!open.isEmpty) {
            val path: List[S] = open.dequeue()
            if (path.head.isSuccess) return Some(path.reverse)
            closed += path.head
            for (x <- path.head.successors)
                if (!closed.contains(x))
                    open.enqueue(x :: path)
        }

        return None
    }

}

object RiverCrossingProblem extends ProblemType {

    type S = CannibalsState

    abstract class CannibalsState extends State {
     //...
    }
    class LeftSideOfRiver extends CannibalsState {
     //...
    }
    class InTransit extends CannibalsState {
     //...
    }
    class RightSideOfRiver extends CannibalsState {
     //...
    }

}