# Finding the first stream of non-repeating elements in Scala (without recursion or side-effects)

Here are some examples:

[1, 2, 3, 4, 5] => [1, 2, 3, 4, 5]
[10, 15, 10, 15, 30] => [10, 15]
[1, 2, 3, 4, 1, 5, 6, 7] => [1, 2, 3, 4]


Here's my best (and deeply ugly) non-recursive, side-effect-free solution so far:

x.scanLeft(List[Int]())((B, Term) => Term :: B).drop(1).takeWhile(i => !(i.tail contains i.head)).last.reverse


Minor optimization:

x.tail.scanLeft(List(x.head))((B, Term) => Term :: B).takeWhile(i => !(i.tail contains i.head)).last.reverse


This is different from distinct:

[1, 2, 3, 4, 1, 5, 6, 7] => [1, 2, 3, 4] and not [1, 2, 3, 4, 5, 6, 7]


Also, considering List[_] is a monoid, isn't there a scan that uses the monoid zero?

This is a fold, not a scan. A scan produces something with the same number of elements, and change the elements. A fold produces something new.

def firstDistinct[T](s: Seq[T]) = s.foldLeft(Seq[T]() -> false) {
case (result @ (_, true), _)           => result
case ((seq, _), el) if seq contains el => seq -> true
case ((seq, _), el)                    => (seq :+ el) -> false
}._1

• Almost... Your solution doesn't work with "infinite" lists, while mine does. I know I didn't said that in the original post, but it's worth mentioning. – Hugo Sereno Ferreira Dec 28 '11 at 17:41
• Nevertheless, amazing display of your functional-fu! – Hugo Sereno Ferreira Dec 28 '11 at 18:18
• @HugoSFerreira Infinite lists are Stream, not List. Might first impulse was going for Stream, but then I noticed you were restricting the solution to List... It should be doable with a lazy foldRight, which, iirc, Scala's isn't but Scalaz has. – Daniel C. Sobral Dec 28 '11 at 21:34
• Thanks for the tip on scalaz. I was already wrapping my head on why foldRight was being strict. – Hugo Sereno Ferreira Dec 29 '11 at 1:37
def once(list:List[Int]) = {
def go(acc:List[Int],set:Set[Int],rest:List[Int]):List[Int]=rest match{
case x::xs if ! set(x) => go(x::acc, set + x, xs)
case _ => acc.reverse
}
go(Nil,Set(),list)
}


And the mandatory one-liner, which would be actually nice if distinct were supported on List.view:

list.zip(list.distinct).takeWhile{case(x,y) => x==y}.map(_._1)


There must be a nice one-liner for Streams, too, but all I got so far is a train wreck...

st.scanLeft((Set[Int](),List[Int]()))((t,x) => if (t._1(x)) null else (t._1+x, x::t._2)).takeWhile(_ != null).last._2.reverse


Edit 2

Basically the same construction idea, but more readable:

st.zip(st.scanLeft(Set[Int]())(_+_)).takeWhile{case(x,s)=> !s(x)}.map(_._1)

• Very nice your one-liner! I'll award the +50... but could you also solve it with infinite lists (streams)? – Hugo Sereno Ferreira Apr 2 '12 at 15:35
    def first_distinct[T](x: Seq[T]) = {
def iter(acc: Seq[T], met: Set[T], rest: Seq[T]): Seq[T] = {
if (rest.isEmpty || (met contains rest.head)) acc