Scala中的等式关系

Question

我刚刚偶然发现了Tony Morris关于Java的博客文章, 以及该语言面临的一个基本问题：为集合定义一种定制的相等关系。我认为这是一件非常重要的事情，想知道是否有Scala的解决方案。

经典的问题体现在思考交易时。假设我进行了两次 +100 vodafone 股票 @150p 的交易。这两笔交易相等，对吗？但它们并不是同一笔交易。在正常的现实系统中，通过持久化或序列化，我不能依靠标识告诉我两个引用是否指向同一笔交易！

因此，我想创建一个集合，可以将等式关系传递给它：

val as = CleverSet[Trade](IdEquality)
val bs = CleverSet[Trade](EconomicsEquality)

我该如何高效地实现我的集合（除非“EqualityRelation”还定义了哈希机制）？

trait EqualityRelation[T] {
  def equal(t1: T, t2: T) : Boolean
  def hash(t: T) : Int
}

所以问题是:

• 是否有提供此功能的库？
• 在Scala中是否有一种整洁的方法来实现这个功能？

似乎使用implicit，将此功能添加到现有的scala Set类型中将会非常容易。

- oxbow_lakes

---

Scalaz中有Equal：http://github.com/scalaz/scalaz/blob/master/example/src/main/scala/scalaz/ExampleEqual.scala。但我不太熟悉它构建在什么基础上。 - Thomas Jung

我认为这只是一个类型安全的等于号，所以"Hello" === 2不能编译。 - oxbow_lakes

scalaz.Equal 不仅是类型安全的，而且还具有灵活性。Equal[List[Foo]] 可以通过 Equal[Foo] 进行参数化。这使得你的目标达成了一半。Martin Odersky 拒绝将 Hash[T] 添加到标准库中，他说：“我们希望保持通用哈希，它太过于 Java 文化的一部分。”http://www.scala-lang.org/node/4091#comment-16327 - retronym

Answer 1

这可以使用Java的TreeSet和Comparator实现来完成：

TreeSet<String> ignoreCase = new TreeSet<String>(new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }});

TreeSet<String> withCase = new TreeSet<String>();

List<String> values = asList("A", "a");
ignoreCase.addAll(values);
withCase.addAll(values);

输出：

ignoreCase -> [A]
withCase -> [A, a]

这种方法的缺点是需要实现比较器的能力比实际需求更强，并且只能使用支持比较器的集合。正如oxbow_lakes所指出的，比较器的实现违反了Set协议（对于!a.equals(b)，可能会出现new Set(); set.add(a) == true && set.add(b) == false）。

Scala通过将A => Ordered[A]进行视图转换来支持此功能。

scala> new scala.collection.immutable.TreeSet[String]()(x=> x.toLowerCase) + "a"
 + "A"
res0: scala.collection.immutable.TreeSet[String] = Set(A)

- Thomas Jung

---

而且你被迫沿着O(log(n))的树形结构访问时间的路线走。 - oxbow_lakes

此外，从TreeSet的JavaDoc中可以看到：请注意，由集合维护的排序（无论是否提供了显式比较器）必须与等式一致，如果要正确实现Set接口，则似乎这种方法可行，但感觉不太对。 - oxbow_lakes

这是一个很有道理的观点。违反Set契约是个坏主意。如果你要把这个TreeSet传递下去，它必须被包装起来。你建议的CleverSet也会以同样的方式破坏它。它只能实现Iterable[T]而不是Set[T]。 - Thomas Jung

仅仅因为Set是基于相等性定义的。哦，我多么希望它是基于（可插拔的）相等关系定义的。 - oxbow_lakes

@oxbow_lakes - 如果你选择这条路（灵活性），那么 java.lang.Object 接口上只会剩下 getClass 方法。 - Thomas Jung

@ThomasJung 听起来像是一个改进 ;) - vossad01

Answer 2

我知道你在问有关Scala的内容，但是将其与.Net集合所提供的内容进行比较是值得的。特别是，所有基于哈希的集合（例如Dictionary<TKey, TValue>和HashSet<T>）都可以采用实现了IEqualityComparer<T>接口的实例。这类似于Scala的Equiv[T]，但还提供了自定义哈希码。你可以通过子类化Equiv来创建一个类似的trait：

trait HashEquiv[T] extends Equiv[T] {
  def hashOf(t: T) : Int
}

为了完全支持基于哈希的集合，它们需要在构造时添加HashEquiv隐式参数，并使用隐式导入的equiv和hashOf方法，而不是Object实例方法（像TreeSet等使用Ordered特质一样，但反过来）。还需要从Any到HashEquiv的隐式转换，该转换使用固有的equals和hashCode实现。

- Ben Lings

Answer 3

你正在描述哈希策略的概念。 Trove库 包含可使用哈希策略构建的集合和映射。

- Craig P. Motlin