Jhonny Everson Jhonny Everson - 1 year ago 86
Scala Question

Remove duplicates in List specifying equality function

I have a

, how is a idiomatic way of removing duplicates given an equality function
(a:A, b:A) => Boolean
? I cannot generally override

The way I can think now is creating a wrapping
class AExt
with overridden
, then

list.map(new AExt(_)).distinct

But I wonder if there's a cleaner way.

Answer Source

I must say I think I'd go via an intermediate collection which was a Set if you expected that your Lists might be quite long as testing for presence (via exists or find) on a Seq is O(n) of course:

Rather than write a custom equals; decide what property the elements are equal by. So instead of:

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

Make a Key. Like so:

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

Then you can add the keys to a Set to see whether you have come across them before.

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

Of course, this solution has worse space complexity and potentially worse performance (as you are creating extra objects - the keys) in the case of very short lists. If you do not like the var in the fold, you might like to look at how you could achieve this using State and Traverse from scalaz 7

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download