SortedSet 映射并不总是保留结果中的元素排序? [英] SortedSet map does not always preserve element ordering in result?

问题描述

给定以下 Scala 2.9.2 代码:

Given the following Scala 2.9.2 code:

更新了非工作示例

import collection.immutable.SortedSet

case class Bar(s: String)

trait Foo {
  val stuff: SortedSet[String]
  def makeBars(bs: Map[String, String])
    = stuff.map(k => Bar(bs.getOrElse(k, "-"))).toList
}

case class Bazz(rawStuff: List[String]) extends Foo {
  val stuff = SortedSet(rawStuff: _*)
}


// test it out....
val b = Bazz(List("A","B","C"))
b.makeBars(Map("A"->"1","B"->"2","C"->"3"))
// List[Bar] = List(Bar(1), Bar(2), Bar(3))
// Looks good?

// Make a really big list not in order. This is why we pass it to a SortedSet...    
val data =  Stream.continually(util.Random.shuffle(List("A","B","C","D","E","F"))).take(100).toList
val b2 = Bazz(data.flatten)

// And how about a sparse map...?
val bs = util.Random.shuffle(Map("A" -> "1", "B" -> "2", "E" -> "5").toList).toMap
b2.makeBars(bs)
// res24: List[Bar] = List(Bar(1), Bar(2), Bar(-), Bar(5))

我发现，在某些情况下，扩展 Foo 的类的 makeBars 方法不返回一个已排序的列表.事实上，列表排序不反映SortedSet

I've discovered that, in some cases, the makeBars method of classes extending Foo does not return a sorted List. In fact, the list ordering does not reflect the ordering of the SortedSet

我在上面的代码中遗漏了什么，其中 Scala 不会总是将 SortedSet 映射到 List，其中元素按 SortedSet 排序?

What am I missing about the above code where Scala will not always map a SortedSet to a List with elements ordered by the SortedSet ordering?

推荐答案

您对隐式解析感到惊讶.

You're being surprised by implicit resolution.

map 方法需要一个与目标集合类型(在简单情况下，与源集合类型相同)和映射器函数的返回类型兼容的 CanBuildFrom 实例.

The map method requires a CanBuildFrom instance that's compatible with the target collection type (in simple cases, identical to the source collection type) and the mapper function's return type.

在 SortedSet 的特殊情况下，其隐含的 CanBuildFrom 要求 Ordering[A](其中 A 是映射器功能)可用.当您的 map 函数返回编译器已经知道如何为其查找 Ordering 的内容时，您就很好:

In the particular case of SortedSet, its implicit CanBuildFrom requires that an Ordering[A] (where A is the return type of the mapper function) be available. When your map function returns something that the compiler already knows how to find an Ordering for, you're good:

scala> val ss = collection.immutable.SortedSet(10,9,8,7,6,5,4,3,2,1)
ss: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 3, 4, 5, 
                                                        6, 7, 8, 9, 10)

scala> val result1 = ss.map(_ * 2)
result1: scala.collection.immutable.SortedSet[Int] = TreeSet(2, 4, 6, 8, 10, 
                                                            12, 14, 16, 18, 20) 
                 // still sorted because Ordering[Int] is readily available

scala> val result2 = ss.map(_ + " is a number")
result2: scala.collection.immutable.SortedSet[String] = TreeSet(1 is a number, 
                                                                10 is a number, 
                                                                2 is a number, 
                                                                3 is a number, 
                                                                4 is a number, 
                                                                5 is a number, 
                                                                6 is a number, 
                                                                7 is a number, 
                                                                8 is a number, 
                                                                9 is a number) 
// The default Ordering[String] is an "asciibetical" sort, 
// so 10 comes between 1 and 2. :)

但是，当您的映射器函数返回一个未知排序的类型时，SortedSet 上的隐式不匹配(具体来说，找不到其隐式参数的值)，因此编译器向上"查找兼容的 CanBuildFrom 并从 Set 中找到通用的.

However, when your mapper function turns out to return a type for which no Ordering is known, the implicit on SortedSet doesn't match (specifically, no value can be found for its implicit parameter), so the compiler looks "upward" for a compatible CanBuildFrom and finds the generic one from Set.

scala> case class Foo(i: Int)
defined class Foo

scala> val result3 = ss.map(Foo(_))
result3: scala.collection.immutable.Set[Foo] = Set(Foo(10), Foo(4), Foo(6), Foo(7), Foo(1), Foo(3), Foo(5), Foo(8), Foo(9), Foo(2))

// The default Set is a hash set, therefore ordering is not preserved

当然，你可以通过简单地提供一个 Ordering[Foo] 的实例来解决这个问题:

Of course, you can get around this by simply supplying an instance of Ordering[Foo] that does whatever you expect:

scala> implicit val fooIsOrdered: Ordering[Foo] = Ordering.by(_.i)
fooIsOrdered: Ordering[Foo] = scala.math.Ordering$$anon$9@7512dbf2

scala> val result4 = ss.map(Foo(_))
result4: scala.collection.immutable.SortedSet[Foo] = TreeSet(Foo(1), Foo(2), 
                                                       Foo(3), Foo(4), Foo(5), 
                                                       Foo(6), Foo(7), Foo(8), 
                                                       Foo(9), Foo(10))
  // And we're back!

最后，请注意玩具示例通常不会出现问题，因为 Scala 集合库对小型 (n <= 6) 集合和映射有特殊实现.

Finally, note that toy examples often don't exhibit the problem, because the Scala collection library has special implementations for small (n <= 6) Sets and Maps.

这篇关于SortedSet 映射并不总是保留结果中的元素排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！