15

我正在做一个练习，以在 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。看起来我需要在and上定义 A ( [A <% Ordered[A]])以及trait 上的视图绑定。但是，我不能在trait 上执行此操作，因为不接受视图边界。BranchLeafTreeNodeTreeNode

据我了解，<%-style view-bounds 是implicit定义的语法糖，因此应该有一种方法可以编写在TreeNode特征中手动定义边界。不过，我不确定我应该怎么做。我环顾四周，但没有比需要定义某种隐式更进一步。

谁能指出我正确的方向？我是否完全从错误的角度来解决这个问题？

4

3 回答 3

24

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

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

请注意，正如 Ben James 所建议的，使用与 an 绑定的上下文Ordering通常比与 an 绑定的视图更好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]]
}

请注意，对于更简洁的定义，您可以等效地定义Leaf如下：

case class Leaf[A](implicit protected val toOrdered: A => Ordered[A]) extends TreeNode[A]
于 2013-01-23T16:22:57.350 回答
15

您可以提供“证据”，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 类型类。但是上述技术的实现是相同的。

于 2013-01-23T16:10:27.807 回答
1

@ben-james's answer is great, I would like improve it a bit to avoid redundant vals in classes.

The idea is to define implicit constructor parameter name the same as it is defined in trait that holds implicit value.

The idea is to avoid this line:

val evidence = ev

Here is a complete example (gist)

trait PrettyPrinted[A] extends (A => String)

object PrettyPrinted {
  def apply[A](f: A => String): PrettyPrinted[A] = f(_)
}

trait Printable[A] {
  implicit def printer: PrettyPrinted[A]
}

// implicit parameter name is important
case class Person(name: String, age: Int)
                 (implicit val printer: PrettyPrinted[Person])
  extends Printable[Person]

object Person {
  implicit val printer: PrettyPrinted[Person] =
    PrettyPrinted { p =>
      s"Person[name = ${p.name}, age = ${p.age}]"
    }
}

// works also with regular classes
class Car(val name: String)
         (implicit val printer: PrettyPrinted[Car])
  extends Printable[Car]

object Car {
  implicit val printer: PrettyPrinted[Car] =
    PrettyPrinted { c =>
      s"Car[name = ${c.name}]"
    }
}
于 2018-03-16T09:05:05.553 回答