Отношения равенства в Scala
Я просто наткнулся на одно из сообщений в блоге Tony Morris о Java и фундаментальной проблеме с языком: это определения сделанного на заказ отношения равенства для набора. Это - что-то, что я думаю, грандиозное предприятие и задалось вопросом, было ли некоторое scala решение.
Классическая проблема проявляется в размышлении о, скажем, торговле. Скажем, я делаю две отрасли +100 долей Vodafone @150p. Две отрасли равны, да? Кроме они не та же торговля. В случае нормальной реальной системы, с персистентностью или сериализацией, я не могу полагаться на идентификационные данные, чтобы сказать мне, являются ли две ссылки к той же торговле!
Таким образом, то, что я хочу, должно смочь создать набор, к которому я могу передать отношение Равенства:
val as = CleverSet[Trade](IdEquality)
val bs = CleverSet[Trade](EconomicsEquality)
Как я реализовал бы свой набор эффективным способом (если EqualityRelation также определяет a hash механизм)?
trait EqualityRelation[T] {
def equal(t1: T, t2: T) : Boolean
def hash(t: T) : Int
}
Таким образом, вопросы:
- Существует ли библиотека, которая обеспечивает эту способность?
- Есть ли некоторый способ сделать это аккуратно в Scala?
Кажется, что с implicits, это была бы вполне легкая вещь добавить к существующему scala Set ввести.
3 ответа
Это уже может быть достигнуто с помощью 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);
Output:
ignoreCase -> [A]
withCase -> [A, a]
Это имеет недостатки, которые Comparator реализует более мощнее, чем необходимо, и что вы ограничены коллекциями, поддерживающими компараторы. Как указано 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)
Я знаю, что вы спрашиваете о Scala, но его стоит сравнить с тем, что предлагают коллекции .Net. В частности, все коллекции на основе хэша (например, Dictionary и HashSet ) могут принимать экземпляр IEqualityComparer . Это похоже на Scala Equiv [T] , но также предоставляет собственный хэш-код. Вы можете создать подобный признак, создав подкласс Equiv :
trait HashEquiv[T] extends Equiv[T] {
def hashOf(t: T) : Int
}
Для полной поддержки коллекции на основе хэшей должны будут добавить неявные параметры HashEquiv в свою конструкцию и использовать неявно импортированные ] Equiv и hashOf вместо методов экземпляра Object (например, TreeSet и т. д. используют черту Ordered ], но наоборот). Также потребуется неявное преобразование из Any в HashEquiv , которое использует внутреннюю реализацию равняется и hashCode .
Вы описываете концепцию стратегии хэширования. Библиотека Trove включает множества и карты, которые могут быть построены с помощью стратегий хэширования.