scala

How to find distinct items in a List in Scala


How in Scala to find distinct items in List?


Solution

  • 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)