How to get distinct items from a Scala Iterable, maintaining laziness

Question

I have a java.lang.Iterable which computes its values lazily. I am accessing it from Scala. Is there a core API way of returning only distinct values? For instance, imaging there was a filter method that also provided all results returned thus far:

val myLazyDistinctIterable = iterable.filter((previousReturnedItems, newItem) => previousReturnedItems.contains(newItem))

I guess this is not a very general case because it involves storing previously returned items, and that might be why it isn't in the core API.

I know about List.distinct and Sets but I want something that will not compute its elements until asked.

Answer 1

You can use the distinct method on Stream. For example, if you have this Iterable:

val it = new java.lang.Iterable[Int] {
  def iterator = new java.util.Iterator[Int] {
    var i = 0
    var first = true

    def hasNext = true
    def next =
      if (first) { first = false; i } else { first = true; i += 1; i - 1 }
    def remove() { throw new UnsupportedOperationException("Can't remove.") }
  }
}

You can write:

scala> import scala.collection.JavaConverters._
import scala.collection.JavaConverters._

scala> val s = it.asScala.toStream
s: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> s.take(10).toList
res0: List[Int] = List(0, 0, 1, 1, 2, 2, 3, 3, 4, 4)

scala> val s = it.asScala.toStream.distinct
s: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> s.take(10).toList
res1: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

We can tell that everything is appropriately lazy since the stream is infinite.

Answer 2

UPDATE Reading questions carefully is good. No laziness in this solution. Sorry.

toSet will do exactly what you want:

1. Store iterated elements in a collection (not what you want but required)
2. Drop / Replace duplicates

Example

val it = Seq(1,2,3,4,2,4): Iterable[Int]
it.toSet
// Set(1,2,3,4)

If you feel fancy, you can convert that back to an iterable:

it.toSet.toIterable

Or, pimp the Iterable:

implicit class UniquableIterable[T](t: Iterable[T]) {
  def unique = t.toSet.toIterable
}

And then call

it.unique