Jhonny Everson Jhonny Everson - 1 month ago 7
Scala Question

Remove duplicates in List specifying equality function

I have a

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


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


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


But I wonder if there's a cleaner way.

Answer

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  }
}).reverse

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

Comments