# 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`?

-
You probably just want the `distinct` method... see stackoverflow.com/questions/1538598/… –  Nicolas Payette Dec 28 '11 at 2:31

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 S Ferreira Dec 28 '11 at 17:41
Nevertheless, amazing display of your functional-fu! –  Hugo S 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 S 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 `Stream`s, 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 S 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
}
iter(Vector.empty, Set.empty, x)
}
``````

This can be optimized, of course (but I'm not sure if compiler does this by itself). I'll write solution for lazy streams some time later.

-
``````val l = List(1,2,3,1,2,3,4)
var s:Set[Int]=Set()
if (s.contains(x))
false
else {
s += x;
true
}
}

res0: List[Int] = List(1, 2, 3)
``````
-
That has side-effects (Set is a var). I'm trying to achieve this functionally. –  Hugo S Ferreira Dec 28 '11 at 12:05