Возвращая тот же тип, функция была передана - PullRequest
Новая
       9

Возвращая тот же тип, функция была передана

2 голосов
/ 17 мая 2010

У меня есть следующая реализация кода поиска в ширину. 

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 выводил, что правильный тип возврата равен CannibalsState, когда ему передан экземпляр LeftSideOfRiver?

Может ли это быть сделано с помощью абстрактного члена типа, или это должно быть сделано с помощью дженериков?

Ответы [ 3 ]

2 голосов
/ 17 мая 2010

Одним из подходов к решению проблемы такого типа является включение признака 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 {
    // ...
  }

}
2 голосов
/ 17 мая 2010

Один из вариантов - использовать дженерики, как описано Рэндаллом. Если вы хотите добиться чего-то похожего с членом абстрактного типа, то вы можете сделать это следующим образом (на основе кода Митча): 

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 {
     //...
    }

}
2 голосов
/ 17 мая 2010

Как насчет этого? 

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