Retour du même type que la fonction a été transmise

Question

J'ai implémenté le code suivant de la recherche Breadth-First.

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 
} 

Si je définis un sous-type de State pour mon problème particulier

class CannibalsState extends State { 
//... 
} 

Quelle est la meilleure façon de faire breadthFirstSearch retourner le même sous-type qui a été adopté?

Et si je change cela pour qu'il y ait 3 différentes classes d'état pour mon problème particulier et ils partagent un supertype commun:

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

Comment puis-je faire les types fonctionnent de telle sorte que breadthFirstSearch infère que le retour correct type est CannibalsState lorsqu'il est passé une instance de LeftSideOfRiver? Est-ce que cela peut être fait avec un membre de type abstrait, ou doit-il être fait avec des génériques?

Answer 1

Une option consiste à utiliser les médicaments génériques comme Randall décrit. Si vous voulez réaliser quelque chose de similaire avec un membre de type abstrait, alors vous pouvez le faire comme ceci (basé sur le code de 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

Que pensez-vous de cela?

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

Une approche de ce type de problème est d'enfermer le trait State et les opérations qui agissent sur elle dans une autre trait.

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 
    } 

} 

Ensuite, vous pouvez définir vos états concrets dans un objet étendant le trait englobante:

object RiverCrossingProblem extends ProblemType { 

    class LeftSideOfRiver extends State { 
    // ... 
    } 

    class InTransit extends State { 
    // ... 
    } 

    class RightSideOfRiver extends State { 
    // ... 
    } 

}