How in Scala to find unique items in List

Question

How in Scala to find unique items in List?

Answer 1

If you refer to the Rosetta Code: Create a Sequence of unique elements

val list = List(1,2,3,4,2,3,4,99)
val l2 = list.removeDuplicates
// l2: scala.List[scala.Int] = List(1,2,3,4,99)

Since List is immutable, you wont modify the initial List by calling removeDuplicates

Warning: as mentioned by this tweet(!), this does not preserve the order:

scala> val list = List(2,1,2,4,2,9,3)
list: List[Int] = List(2, 1, 2, 4, 2, 9, 3)

scala> val l2 = list.removeDuplicates
l2: List[Int] = List(1, 4, 2, 9, 3)

For a Seq, that method should be available in Scala2.8, according to ticket 929.
In the meantime, you will need to define an ad-hoc static method as the one seen here

Answer 2

A simple ad-hoc method is just to add the List to a Set, and use from there:

  val l = List(1,2,3,3,3,4,5,5,6,7,8,8,8,9,9)
  val s = Set() ++ x
  println(s)

Produces:

> Set(5, 1, 6, 9, 2, 7, 3, 8, 4)

This works for a Seq (or any Iterable), but is not necessary in 2.8, where the removeDuplicates method will probably be more readable. Also, not sure about the runtime performance vs a more thought-out conversion.

Also, note the lost ordering.

Answer 3

Roll your own uniq filter with order retention:

scala> val l = List(1,2,3,3,4,6,5,6)
l: List[Int] = List(1, 2, 3, 3, 4, 6, 5, 6)

scala> l.foldLeft(Nil: List[Int]) {(acc, next) => if (acc contains next) acc else next :: acc }.reverse
res0: List[Int] = List(1, 2, 3, 4, 6, 5)

Answer 4

The most efficient order-preserving way of doing this would be to use a Set as an ancillary data structure:

def unique[A](ls: List[A]) = {
  def loop(set: Set[A], ls: List[A]): List[A] = ls match {
    case hd :: tail if set contains hd => loop(set, tail)
    case hd :: tail => hd :: loop(set + hd, tail)
    case Nil => Nil
  }

  loop(Set(), ls)
}

We can wrap this in some nicer syntax using an implicit conversion:

implicit def listToSyntax[A](ls: List[A]) = new {
  def unique = unique(ls)
}

List(1, 1, 2, 3, 4, 5, 4).unique    // => List(1, 2, 3, 4, 5)

Answer 5

in 2.8, it's List(1,2,3,2,1).distinct