Удалить дубликаты в списке, указав функцию равенства

Ответ 1

Я должен сказать, что я бы пошел через промежуточную коллекцию, которая была Set, если бы вы ожидали, что ваш List может быть довольно длинным, как тестирование для присутствия (через exists или find) на Seq - O (n), конечно:

Вместо того, чтобы писать пользовательские равно; решить, какое свойство элементы равны. Поэтому вместо:

def myCustomEqual(a1: A, a2: A) = a1.foo == a2.foo && a1.bar == a2.bar

Сделайте ключ. Например:

type Key = (Foo, Bar)
def key(a: A) = (a.foo, a.bar)

Затем вы можете добавить ключи к Set, чтобы увидеть, встречались ли вы раньше.

var keys = Set.empty[Key]
((List.empty[A] /: as) { (l, a) => 
  val k = key(a)
  if (keys(k)) l else { keys += k; a +: l  }
}).reverse

Конечно, это решение имеет худшую космическую сложность и потенциально худшую производительность (поскольку вы создаете дополнительные объекты - ключи) в случае очень коротких списков. Если вам не нравится var в сгибе, вам может понравиться, как вы могли бы достичь этого, используя State и Traverse из scalaz 7

Ответ 2

Существует простой (более простой) способ сделать это:

list.groupBy(_.key).mapValues(_.head)

Если вы хотите, вы можете использовать полученную карту мгновенно, заменив _.head на функциональный блок, например:

sameElements => { val observedItem = sameElements.head
                  new A (var1 = observedItem.firstAttr,
                         var2 = "SomethingElse") }

чтобы вернуть новый A для каждого отдельного элемента.

Есть только одна незначительная проблема. Вышеприведенный код (list.groupBy(_.key).mapValues(_.head)) не очень хорошо объяснил намерение удалить дубликаты. По этой причине было бы здорово иметь такую ​​функцию, как distinctIn[A](attr: A => B) или distinctBy[A](eq: (A, A) -> Boolean).

Ответ 3

Используя Foo и customEquals из ответа misingFaktor:

  case class Foo(a: Int, b: Int)
  val (a, b, c, d) = (Foo(3, 4), Foo(3, 1), Foo(2, 5), Foo(2, 5))
  def customEquals(x: Foo, y: Foo) = x.a == y.a

  (Seq(a, b, c, d).foldLeft(Seq[Foo]()) {
    (unique, curr) => {
      if (!unique.exists(customEquals(curr, _)))
        curr +: unique
      else
        unique
    }
  }).reverse

Если упорядочение результата важно, но дубликат, который нужно удалить, нет, тогда рекомендуется сделать foldRight

  Seq(a, b, c, d).foldRight(Seq[Foo]()) {
    (curr, unique) => {
      if (!unique.exists(customEquals(curr, _)))
        curr +: unique
      else
        unique
    }
  }

Ответ 4

scala> case class Foo(a: Int, b: Int)
defined class Foo

scala> val (a, b, c, d) = (Foo(3, 4), Foo(3, 1), Foo(2, 5), Foo(2, 5))
a: Foo = Foo(3,4)
b: Foo = Foo(3,1)
c: Foo = Foo(2,5)
d: Foo = Foo(2,5)

scala> def customEquals(x: Foo, y: Foo) = x.a == y.a
customEquals: (x: Foo, y: Foo)Boolean

scala> Seq(a, b, c, d) filter {
     |   var seq = Seq.empty[Foo]
     |   x => {
     |    if(seq.exists(customEquals(x, _))) {
     |      false 
     |    } else { 
     |      seq :+= x
     |      true 
     |    }
     | }
res13: Seq[Foo] = List(Foo(3,4), Foo(2,5))

Ответ 5

case class Foo (a: Int, b: Int)

val x = List(Foo(3,4), Foo(3,1), Foo(2,5), Foo(2,5))
def customEquals(x : Foo, y: Foo) = (x.a == y.a && x.b == y.b)

x.foldLeft(Nil : List[Foo]) {(list, item) => 
   val exists = list.find(x => customEquals(item, x))
   if (exists.isEmpty) item :: list
   else list
 }.reverse

res0: Список [Foo] = Список (Foo (3,4), Foo (3,1), Foo (2,5))