代码之家 › 专栏 › 技术社区 › Ken Bloom

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

type-systems types scala

Ken Bloom · 技术社区 · 16 年前

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 返回与传递的子类型相同的子类型?

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

我怎样才能把这些类型弄清楚呢 横向优先搜索 推断正确的返回类型是 CannibalsState 当它传递一个 LeftSideOfRiver ?

3 回复 | 直到 16 年前

Sandor Murakozi 16 年前

一种选择是使用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 {
     //...
    }

}

Randall Schulz 16 年前

这个怎么样?

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

Mitch Blevins 16 年前

解决这类问题的一种方法是将 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 {
    // ...
  }

}