返回相同类型的功能已通过

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个不同的状态类，它们都有一个共同的超类型：

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

我怎样才能让工种出来，这样breadthFirstSearch推断正确的返回当它通过LeftSideOfRiver的实例时，类型为CannibalsState？

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

Answer 1

一种选择是兰德尔描述使用泛型。如果你想实现与抽象类型成员类似的事情，那么你可以这样做（基于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 { 
    //... 
    } 

} 

Answer 2

这个怎么样？

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

object BFS 
{ 
    def 
    breadthFirstSearch[S <: State[S]](initial: State[S]): Option[List[State[S]]] = { 
    val open= new scala.collection.mutable.Queue[List[State[S]]] 
    val closed = new scala.collection.mutable.HashSet[State[S]] 

    open.enqueue(initial :: Nil) 

    while (!open.isEmpty) { 
     val path: List[State[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 
    } 
} 

Answer 3

一种方法这种类型的问题是封闭State特质和另一个特质内作用于它的操作。

trait ProblemType { 

    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 
    } 

} 

然后，您可以延长封闭特征的对象中定义您的具体状态：

object RiverCrossingProblem extends ProblemType { 

    class LeftSideOfRiver extends State { 
    // ... 
    } 

    class InTransit extends State { 
    // ... 
    } 

    class RightSideOfRiver extends State { 
    // ... 
    } 

}