在Scala特征上定义隐式视图边界

Question

我正在练习在Scala中实现一个功能二进制搜索树,遵循我在Haskell中看到的类似模式.我有一个看起来像这样的结构:

trait TreeNode[A] {
    def isLeaf: Boolean
    def traverse: Seq[A]
    ...
}

case class Branch[A](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   def isLeaf: Boolean = false
   def traverse: Seq[A] = ...
   ... 
}

case class Leaf[A]() extends TreeNode[A] { 
    def isLeaf: Boolean = true
    def traverse: Seq[A] = Seq[A]()
    ... 
}

我喜欢把一个类型约束上A,以便它仅接受扩展对象Ordered.它看起来像我需要定义绑定,该视图([A <% Ordered[A]])上Branch和Leaf,还有TreeNode特质.我不能做到这一点的TreeNode特征,但是,因为鉴于界限是不能接受的.

据我所知,<%-style视图边界是implicit定义的语法糖,因此应该有一种方法来编写以在TreeNodetrait中手动定义绑定.不过,我不确定我该怎么做.我已经环顾了一下,但没有进一步深入,需要定义一些隐含的需求.

任何人都能指出我正确的方向吗？我是从错误的角度接近这个吗？

Answer 1

问题是视图边界和上下文边界只是特定类型的隐式参数的语法糖.当应用于泛型类的类型参数时(与应用于泛型方法时相反),这些含义将添加到类的构造函数中.因为traits没有构造函数(或者更确切地说,只有一个无参数构造函数),所以无处可传递这些隐式参数,因此上下文边界和视图边界在通用特征上是非法的.最简单的解决方案是TreeNode变成一个抽象类:

abstract class TreeNode[A <% Ordered[A]]

请注意,正如Ben James所建议的那样,使用与a绑定的上下文Ordering通常比使用绑定的视图更好Ordered(它更通用).然而问题仍然是相同的:不会对特性起作用.

如果TreeNode变成一个类是不实际的(比如你需要在类型层次结构中的不同位置混合它),你可以定义一个抽象方法TreeNode,它将提供隐式值(类型Ordered[A])并且具有扩展它的所有类定义它.不幸的是,这更加冗长和明确,但在这种情况下你不能做得更好:

trait TreeNode[A] {
  implicit protected def toOrdered: A => Ordered[A]
}

case class Branch[A<%Ordered[A]](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   protected def toOrdered = implicitly[A => Ordered[A]]
}

case class Leaf[A<%Ordered[A]]() extends TreeNode[A] { 
    protected def toOrdered = implicitly[A => Ordered[A]]
}

Answer 2

你可以提供"证据",A是Ordered通过要求类型的抽象成员Ordered[A]在trait:

trait TreeNode[A] {
  implicit val evidence: Ordered[A]
}

然后,您将被迫在任何具体的子类型提供了这一点,这证明A是Ordered:

case class Leaf[A](value: A)(implicit ev: Ordered[A]) extends TreeNode[A] {
  val evidence = ev
}

您可能希望将约束限制A为具有隐式的类型Ordering[A]- 这不是继承关系; 它更像是一个haskell类型类.但就上述技术而言,实施方案将是相同的.