How in Scala to find distinct items in List?
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)