Равенство отношений в Скала - PullRequest
Новая
       32

Равенство отношений в Скала

8 голосов
/ 26 февраля 2010

Я только что наткнулся на одно из сообщений в блоге Тони Морриса о Java и о фундаментальной проблеме с языком: об определении индивидуального отношения равенства для коллекции. Я думаю, что это большое дело , и мне было интересно, было ли какое-то решение от scala.

Классическая проблема проявляется в размышлениях, скажем, о торговле. Допустим, я совершил две сделки по +100 акциям vodafone при 150 пенсов. Две сделки равны, да? За исключением того, что они не одна и та же торговля . В случае нормальной реальной системы с постоянством или сериализацией я не могу полагаться на identity , чтобы сказать мне, являются ли две ссылки на одной и той же сделкой !

Итак, я хочу создать коллекцию, в которую я могу передать отношение равенства: 

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

Как мне эффективно реализовать мой набор (если EqualityRelation также не определяет механизм hash)? 

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

Итак, вопросы:

  • Есть ли библиотека, которая предоставляет эту возможность?
  • Есть ли какой-нибудь способ сделать это аккуратно в Scala?

Похоже, с учетом этого было бы довольно легко добавить существующий тип Set в scala.

Ответы [ 3 ]

6 голосов
/ 26 февраля 2010

Это уже может быть достигнуто с помощью 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, реализация Comparator нарушает контракт 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)
2 голосов
/ 27 февраля 2010

Я знаю, что вы спрашиваете о Scala, но стоит сравнить с тем, что предлагают коллекции .Net.В частности, все коллекции на основе хеша (например, Dictionary<TKey, TValue> и HashSet<T>) могут иметь экземпляр IEqualityComparer<T>.Это похоже на Equiv[T] в Scala, но также предоставляет собственный хэш-код.Вы можете создать аналогичную черту, создав подкласс Equiv: 

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

. Для полной поддержки коллекциям на основе хеша потребуется добавить неявные параметры HashEquiv в их конструкцию и использовать неявно импортированные equiv иhashOf методы вместо Object методов экземпляра (например, TreeSet и т. Д. С чертой Ordered, но в обратном порядке).Также должно быть неявное преобразование из Any в HashEquiv, использующее внутреннюю реализацию equals и hashCode.

2 голосов
/ 26 февраля 2010

Вы описываете концепцию стратегии хеширования. Библиотека Trove включает в себя наборы и карты, которые можно создавать с помощью стратегий хеширования.

...