CODEWITHSUNDEEP
scalacollections
user445107
user445107

Reputation:

How to take the first distinct (until the moment) elements of a list?

I am sure there is an elegant/funny way of doing it, but I can only think of a more or less complicated recursive solution.

Rephrasing: Is there any standard lib (collections) method nor simple combination of them to take the first distinct elements of a list?

scala> val s = Seq(3, 5, 4, 1, 5, 7, 1, 2)
s: Seq[Int] = List(3, 5, 4, 1, 5, 7, 1, 2)

scala> s.takeWhileDistinct //Would return Seq(3,5,4,1), it should preserve the original order and ignore posterior occurrences of distinct values like 7 and 2.

Upvotes: 6

Views: 879

Answers (5)

user445107
user445107

Reputation:

The problem is simpler than the std lib function I was looking for (takeWhileConditionOverListOfAllAlreadyTraversedItems):

scala> val s = Seq(3, 5, 4, 1, 5, 7, 1, 2)
scala> s.zip(s.distinct).takeWhile{case(a,b)=>a==b}.map(_._1)
res20: Seq[Int] = List(3, 5, 4, 1)

Upvotes: 1

Kevin Wright
Kevin Wright

Reputation: 49705

A variation on Rex's (though I prefer his...)

This one is functional throughout, using the little-seen scanLeft method.

val prevs = xs.scanLeft(Set.empty[Int])(_ + _)
(xs zip prevs) takeWhile { case (x,prev) => !prev(x) } map {_._1}

UPDATE

And a lazy version (using iterators, for moar efficiency):

val prevs = xs.iterator.scanLeft(Set.empty[Int])(_ + _)
(prevs zip xs.iterator) takeWhile { case (prev,x) => !prev(x) } map {_._2}

Turn the resulting iterator back to a sequence if you want, but this'll also work nicely with iterators on both the input AND the output.

Upvotes: 0

Rex Kerr
Rex Kerr

Reputation: 167891

If you want it to be fast-ish, then

{ val hs = scala.collection.mutable.HashSet[Int]()
  s.takeWhile{ hs.add } }

will do the trick. (Extra braces prevent leaking the temp value hs.)

Upvotes: 8

flavian
flavian

Reputation: 28511

This is a short approach in a maximum of O(2logN).

implicit class ListOps[T](val s: Seq[T]) {
    def takeWhileDistinct: Seq[T] = {
      s.indexWhere(x => { s.count(x==) > 1 }) match {
        case ind if (ind > 0) => s.take(
          s.indexWhere(x => { s.count(x==) > 1 }, ind + 1) + ind).distinct
        case _ => s
      }
    }
  }

val ex = Seq(3, 5, 4, 5, 7, 1)
val ex2 = Seq(3, 5, 4, 1, 5, 7, 1, 5) 

println(ex.takeWhileDistinct.mkString(", ")) // 3, 4, 5
println(ex2.takeWhileDistinct.mkString(", ")) // 3, 4, 5, 1

Look here for live results.

Upvotes: 2

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297195

Interesting problem. Here's an alternative. First, let's get the stream of s so we can avoid unnecessary work (though the overhead is likely to be greater than the saved work, sadly).

val s = Seq(3, 5, 4, 5, 7, 1)
val ss = s.toStream

Now we can build s again, but keeping track of whether there are repetitions or not, and stopping at the first one:

val newS = ss.scanLeft(Seq[Int]() -> false) { 
  case ((seen, stop), current) => 
    if (stop || (seen contains current)) (seen, true) 
    else ((seen :+ current, false)) 
}

Now all that's left is take the last element without repetition, and drop the flag:

val noRepetitionsS = newS.takeWhile(!_._2).last._1

Upvotes: 1

Related Questions