将小写字母放入集合时的区别

Question

为什么将小写字母放入 Set 会有所不同？

Haskell

λ: import Data.Set as S
λ: Prelude.foldr (\e acc -> S.insert e acc) S.empty ['a' .. 'z']
fromList "abcdefghijklmnopqrstuvwxyz"

Scala

scala> ('a' to 'z').toList.toSet
res5: scala.collection.immutable.Set[Char] = Set(e, s, x, n, j, y, t,               
     u, f, a, m, i, v, q, b, g, l, p, c, h, r, w, k, o, z, d)

Answer 1

scala默认的set实现是hash set，所以是无序的。 Haskell 中的默认集合实现是有序集合。（您需要一个 Ord 实例来插入新元素：insert :: Ord a => a -> Set a -> Set a）

要在 Scala 中保持顺序，您必须使用 SortedSet，如下所示：

scala> import scala.collection.immutable._
scala> ('a' to 'z').to[SortedSet]
res4: scala.collection.immutable.SortedSet[Char] = TreeSet(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)

这里有一些关于不同选择的背景知识：

Scala 选择基于哈希的实现，因为这在 JVM 世界中很常见，而且哈希表通常比排序集合快很多。这样做的缺点是哈希码引入了一些不确定性，尤其是与使用默认哈希码实现的类结合使用时。

Haskell 将纯度置于性能之上，因此它选择更具确定性的排序集合。

Answer 2

Set只是一个名称，描述了一种无序且不允许重复元素的数据结构。其他一切基本上都取决于实现。

您现在已经体验到 Haskell 中的 Set 是有序的，即它的元素需要一个 Ord 实例来定义它们的小于关系。 Scala 对 Set 特性的默认实现似乎是一个 HashSet，因此顺序似乎是随机的；实际上它反映了桶元素的顺序。

在许多情况下，当集合是正确的数据结构时，排序并不重要（检查成员资格、跟踪不同对象的数量，...）。如果是这样，Scala 中有专门的选项比 Set 特性具有更严格的合同，就像 Java：SortedSet 对于具有逻辑顺序的元素，或 LinkedHashSet]，它保留迭代的插入顺序，但使用哈希集数据结构进行通常的集合操作。

将小写字母放入集合时的区别

Difference when Putting Lower-cased Alphabet into Set

haskell

scala

set