Type-safety for Patternmatching on Parameters with Dependent Types in Scala-CodePudding

I am currently working with a type hierarchy which represents a tree and an accompanying type hierarchy that represents steps of root-to-node paths in that tree. There are different kinds of nodes so different steps can be taken at each node. Therefore, the node types have a type member which is set to a trait including all valid steps. Take the following example:

// Steps
sealed trait Step
sealed trait LeafStep extends Step
sealed trait HorizontalStep extends Step
sealed trait VerticalStep extends Step
object Left extends HorizontalStep
object Right extends HorizontalStep
object Up extends VerticalStep
object Down extends VerticalStep

// The Tree
sealed trait Tree {
  type PathType <: Step
}
case class Leaf() extends Tree {
  override type PathType = LeafStep
}
case class Horizontal(left: Tree, right: Tree) extends Tree {
  override type PathType = HorizontalStep
}
case class Vertical(up: Tree, down: Tree) extends Tree {
  override type PathType = VerticalStep
}

In this example, given a tree the path Seq(Up, Right) would tell us to go to the "right" child of the "up" child of the root (assuming the tree's nodes have the fitting types). Of course, navigating the tree involves a bunch of code using PartialFunctions that is not shown in the example. However, in that process I want to provide a type-safe callback which is notified for every step that is taken and its arguments include both the step and the respective tree nodes.

My current approach is a function def callback(from: Tree, to: Tree)(step: from.PathType). That works without problems on the caller side, but I'm running into an issue when actually implementing such a callback that works with the data passed to it.

def callback(from: Tree, to: Tree)(step: from.PathType) = {
  from match {
    case f: Horizontal => step match {
      case Left => ??? // do useful stuff here
      case Right => ??? // do other useful stuff here
    }
    case _ => ()
  }
}

In the function, the compiler is not convinced that Left and Right are of type from.PathType. Of course, I could simply add .asInstanceOf[f.PathType] and the code seems to work with that. However, the outer match gives us that f is of type Horizontal. We know that PathType of Horizontal objects is HorizontalStep and since f is identical to from we also know that from.PathType is of that same type. Finally, we can check that both Left and Right extend HorizontalStep. So, the above code should always be type-safe even without the cast.

Is that reasoning something the Scala compiler just does not check or am I missing a case where the types could differ? Is there a better way to achieve my goal of a type-safe callback? I'm using Scala 2.12.15

CodePudding user response：

I'm afraid I do not have a thorough explanation on why this does not typecheck. (It seems as if for such dependent-typed parameters, the compiler just isn't able to apply the knowledge that was gained from pattern matching onto the other parameter (that was not explictly matched)).

Nevertheless, here is something that would work:

First, use a type parameter instead of a type member:

// (Steps as above)
// The Tree
sealed trait Tree[PathType <: Step]

// type alias to keep parameter lists simpler
// where we do not care..
type AnyTree = Tree[_ <: Step]

case class Leaf() extends Tree[LeafStep]

case class Horizontal(left: AnyTree, right: AnyTree) extends Tree[HorizontalStep]

case class Vertical(up: AnyTree, down: AnyTree) extends Tree[VerticalStep]

Then, this would fully typecheck:

def callback[S <: Step, F <: Tree[S]](from: F, to: AnyTree)(step: S) = {
  def horizontalCallback(from: Horizontal)(step: HorizontalStep) = {
    step match {
      case Left => ??? // do useful stuff here
      case Right => ??? // do other useful stuff here
    }
  }
  from match {
    case f: Horizontal =>
      horizontalCallback(f)(step)
    case _ =>
      ()
  }
}

Confusingly, the compiler would not be able to properly check the pattern match on the step if one places it directly in the outer match like this (Edit: that is only true for 2.12 where this does not give a "match may not be exhaustive" warning - with 2.13 or 3.2, this checks fine):

def callback[S <: Step, F <: Tree[S]](from: F, to: AnyTree)(step: S) = {
  from match {
    case f: Horizontal =>
      step match {
        case Left => ??? // do useful stuff here
        case Right => ??? // do other useful stuff here
      }
    case _ =>
      ()
  }
}