6

（我正在使用 Scala nightlies，并在 2.8.0b1 RC4 中看到相同的行为。我是 Scala 新手。）

我有两个SortedMap要组成联合的 s。这是我想使用的代码：

import scala.collection._

object ViewBoundExample {
    class X
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = {
        a ++ b
    }
    implicit def orderedX(x: X): Ordered[X] = new Ordered[X] { def compare(that: X) = 0 }
}

这里的想法是“隐式”语句意味着Xs 可以转换为s，然后将s 组合成另一个Ordered[X]是有意义的，而不仅仅是一个映射。SortedMapSortedMap

当我编译时，我得到

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac -versionScala compiler version
2.8.0.Beta1-RC4 -- Copyright 2002-2010, LAMP/EPFL

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac ViewBoundExample.scala
ViewBoundExample.scala:8: error: type arguments [ViewBoundExample.X] do not
    conform to method ordered's type parameter bounds [A <: scala.math.Ordered[A]]
        a ++ b
          ^
one error found

如果该类型参数绑定是[A <% scala.math.Ordered[A]]，而不是[A <: scala.math.Ordered[A]]. 不幸的是，我什至无法弄清楚“有序”方法的位置！任何人都可以帮我追踪它吗？

如果做不到这一点，我该怎么做才能产生两个SortedMaps 的并集？如果我删除 combine 的返回类型（或将其更改为Map）一切正常 --- 但是我不能依赖返回被排序！

4

2 回答 2

5

目前，您使用的是scala.collection.SortedMap特征，其++方法是从特征继承的MapLike。因此，您会看到以下行为：

scala> import scala.collection.SortedMap
import scala.collection.SortedMap

scala> val a = SortedMap(1->2, 3->4)
a: scala.collection.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> val b = SortedMap(2->3, 4->5)
b: scala.collection.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5)

scala> a ++ b
res0: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

scala> b ++ a
res1: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

的返回结果的类型++是 a ，因为这将是唯一对返回对象的方法Map[Int, Int]有意义的类型。似乎保留了 sorted 的属性，我猜这是因为使用抽象方法进行连接，并且这些抽象方法被定义为保持地图的顺序。++MapLike++SortedMap++

要合并两个已排序的地图，我建议您使用scala.collection.immutable.SortedMap.

scala> import scala.collection.immutable.SortedMap
import scala.collection.immutable.SortedMap

scala> val a = SortedMap(1->2, 3->4)
a: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> val b = SortedMap(2->3, 4->5)
b: scala.collection.immutable.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5)

scala> a ++ b
res2: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

scala> b ++ a
res3: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

这个SortedMaptrait 的实现声明了一个++返回 a 的方法SortedMap。

现在有几个关于类型界限的问题的答案：

  • Ordered[T]是一个特征，如果混合在一个类中，它指定该类可以使用<, >, =, >=,进行比较<=。您只需要定义compare(that: T)返回-1for this < that、1forthis > that和0for的抽象方法this == that。然后所有其他方法都根据compare.

  • T <% U表示在 Scala 中绑定的视图。这意味着类型T要么是的子类型，U要么可以U通过范围内的隐式转换隐式转换为。如果您放置<%但不使用<:asX不是子类型Ordered[X]但可以Ordered[X]使用隐OrderedX式转换隐式转换，则该代码有效。

编辑：关于你的评论。如果您scala.collection.immutable.SortedMap正在SortedMap使用trait. 您可以将其视为 的更专业的特征scala.collection.SortedMap，它提供了额外的操作（如++返回 a SortedMap）和不可变的属性。这符合 Scala 哲学——更喜欢不可变性——因此我认为使用 immutable 没有任何问题SortedMap。在这种情况下，您可以保证结果肯定会排序，并且由于集合是不可变的，因此无法更改。

不过，我仍然觉得奇怪的是，scala.collection.SortedMap不提供++方法，因此女巫返回 a SortedMap。我所做的所有有限测试似乎表明两个scala.collection.SortedMaps 的串联结果确实会产生一个保留排序属性的映射。

于 2009-12-21T12:59:56.460 回答
4

作为 Scala 的初学者，您是否选择了一个难以破解的难题！:-)

好的，简短的游览，不要指望现在完全理解它。首先，请注意问题发生在方法上++。搜索它的定义，我们在 trait 处找到它MapLike，接收 anIterator或 a Traversable。既然y是 a SortedMap，那么它就是Traversable正在使用的版本。

请注意，在其广泛的类型签名中，有一个CanBuildFrom正在传递。它是隐式传递的，所以你通常不需要担心它。但是，要了解正在发生的事情，这次你要做。

您可以通过单击它出现在定义中的 CanBuildFrom++或通过过滤来找到它。正如 Randall 在评论中提到的那样，scaladoc 页面的左上角有一个未标记的空白字段。您只需单击此处并输入，它就会返回您输入的任何内容的匹配项。

因此，CanBuildFrom在 ScalaDoc 上查找特征并选择它。它有大量子类，每个子类负责构建特定类型的集合。搜索并单击子类SortedMapCanBuildFrom。这是您需要SortedMap从 a生成 a 的对象的类Traversable。请注意它接收隐式Ordering参数的实例构造函数（类的构造函数）。现在我们越来越近了。

这一次，使用过滤器过滤器来搜索Ordering. 它的伴生对象（单击名称中的小“o”）承载将生成Orderings 的隐含对象，因为会检查伴生对象是否为该类生成实例或转换的隐含对象。它在 trait 中定义LowPriorityOrderingImplicits，对象Ordering扩展，查看它你会看到 method ordered[A <: Ordered[A]]，它将产生Ordering所需的......或者如果没有问题，就会产生它。

有人可能会假设隐式转换从XtoOrdered[X]就足够了，就像我在更仔细地研究之前所做的那样。然而，这是对objects的转换，并且ordered期望接收​​一个是 的子类型的类型Ordered[X]。虽然可以将类型的对象转换为类型X的对象Ordered[X]，X但它本身不是 的子类型Ordered[X]，因此它不能作为参数传递给ordered。

另一方面，您可以创建一个隐含val Ordering[X]的 , 而不是def Ordered[X]，您将解决这个问题。具体来说：

object ViewBoundExample {
    class X
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = {
        a ++ b
    }
    implicit val orderingX = new Ordering[X] { def compare(x: X, y: X) = 0 }
}

Ordered我认为大多数人对/的最初反应Ordering一定是困惑之一：为什么要为同一件事开设课程？前者延伸java.lang.Comparable，而后者延伸java.util.Comparator。唉，类型签名compare几乎总结了主要区别：

def compare(that: A): Int     // Ordered
def compare(x: T, y: T): Int  // Ordering

使用 anOrdered[A]需要A扩展Ordered[A]，这需要能够修改 A的定义，或者传递可以将 an 转换A为 的方法Ordered[A]。Scala 完全有能力轻松完成后者，但是您必须在比较之前转换每个实例。

另一方面，使用Ordering[A]需要创建单个对象，如上所示。当您使用它时，您只需将两个类型的对象传递A给compare- 在此过程中不会创建任何对象。

Ordering所以会有一些性能提升，但 Scala 偏爱over有一个更重要的原因Ordered。再看一下伴随对象到Ordering。您会注意到其中定义的许多 Scala 类有几个隐式。您可能还记得我之前提到过，T将在 的伴随对象中搜索隐式 for 类T，而这正是正在发生的事情。

这也可以做到Ordered。然而，这就是症结所在，这意味着支持这两种方法的每种方法Ordering都会Ordered失败！那是因为 Scala 会寻找一个隐式来使其工作，并且会找到两个：一个 for Ordering，一个 for Ordered。由于无法确定您想要哪个，Scala 放弃了一条错误消息。因此，必须做出选择，并为此做出Ordering更多选择。

呃，我忘了解释为什么签名没有被定义为ordered[A <% Ordered[A]]，而不是ordered[A <: Ordered[A]]。我怀疑这样做会导致我之前提到的双重隐含失败，但我会问真正做过这些事情并遇到双重隐含问题的人，这种特定方法是否有问题。

于 2009-12-21T12:28:14.560 回答