Returning the same type, the function was passed
I have the following implementation of Breadth-First search code.
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
}
If I define a subtype State
for my specific problem
class CannibalsState extends State {
//...
}
What's the best way to make it breadthFirstSearch
return the same subtype that was passed in?
Suppose I change this so that there are 3 different state classes for my specific task, and they have a common supertype:
abstract class CannibalsState extends State {
//...
}
class LeftSideOfRiver extends CannibalsState {
//...
}
class InTransit extends CannibalsState {
//...
}
class RightSideOfRiver extends CannibalsState {
//...
}
How can I get the types to work so that it breadthFirstSearch
indicates that the correct return type is CannibalsState
when it passed the instance LeftSideOfRiver
?
Can this be done with an element of an abstract type, or should it be done using generics?
a source to share
One option is to use generics as described by Randall. If you want to achieve something similar with an abstract type element, you can do it like this (based on Mitch's code):
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 {
//...
}
}
a source to share
How about this?
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
}
}
a source to share
One approach to this problem is to enclose the line State
and the operations acting on it within another feature.
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
}
}
You can then define your specific states in an object extending the encompassing trait:
object RiverCrossingProblem extends ProblemType {
class LeftSideOfRiver extends State {
// ...
}
class InTransit extends State {
// ...
}
class RightSideOfRiver extends State {
// ...
}
}
a source to share