No type in scala priority queue
I am using a priority queue to order a case class called TreeNodeWithCostAndHeuristic
case class TreeNodeWithCostAndHeuristic[S,A](parent:Option[TreeNodeWithCostAndHeuristic[S,A]],
action: Option[A],
state: S,
cost: Double,
estimatedRemainingCost: Double)
This priority queue is created inside a function that uses its parameter to set the initial state, while other values should be stored as None or 0
def HeuristicGraphSearch[S,A](problem: ProblemWithCostAndHeuristic[S,A]) = {
val root = TreeNodeWithCostAndHeuristic(parent = None,action=None,state=problem.initialState,cost = 0.0, estimatedRemainingCost = 0.0)
val frontier : mutable.PriorityQueue[TreeNodeWithCostAndHeuristic[S,A]] = mutable.PriorityQueue.empty[TreeNodeWithCostAndHeuristic[S,A]]
frontier.enqueue(root)
However, due to the parent and action missing, I get a mismatch between the expected type TreeNodeWithCostAndHeuristic[S,A]
and the one I am trying to enqueue TreeNodeWithCostAndHeuristic[S,Nothing]
.
As far as I know, nothing is a subtype of Option, and in my case the class and the parent and the action are parameters. Why am I getting a mismatch?
source to share
It has to do with how the Scala compiler types. The short answer is to just help it a bit by explicitly declaring the types when constructing your case class:
val root = TreeNodeWithCostAndHeuristic[S, A](parent = None,action=None,state=problem.initialState,cost = 0.0, estimatedRemainingCost = 0.0)
The reason TreeNodeWithCostAndHeuristic[S, Nothing]
it is not considered a valid replacement TreeNodeWithCostAndHeuristic[S, A]
is because it is not a subclass of it; to be one, it must be covariant in type A. If some is Foo[A]
covariant in its type A
, then only then the following holds: Foo[S] <: Foo[A]
for anyone S
that is a subclass A
.
source to share
In addition to sloucs answer, you can also use the description type to help the compiler:
val root = TreeNodeWithCostAndHeuristic(
parent = None: Option[TreeNodeWithCostAndHeuristic[S, A]],
action = None: Option[A],
state = problem.initialState,
cost = 0.0,
estimatedRemainingCost = 0.0)
The reason the compiler complains is that it cannot guarantee what None.type
is Option[TreeNodeWithCostAndHeuristic[S, A]]
and Option[A]
, accordingly, and thus it "folds" and outputs Nothing
which is the bottom type of all types.
@Dima also suggests using Option.empty[A]
:
val root = TreeNodeWithCostAndHeuristic(
parent = Option.empty,
action = Option.empty[A],
state = problem.initialState,
cost = 0.0,
estimatedRemainingCost = 0.0)
source to share