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

Question

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?

• Nicolas Payette: You probably just want the distinct method... see stackoverflow.com/questions/1538598/…

Answer 1

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

• Hugo Sereno Ferreira: 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: Nevertheless, amazing display of your functional-fu!
• Daniel C. Sobral: @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.
• Hugo Sereno Ferreira: Thanks for the tip on scalaz. I was already wrapping my head on why foldRight was being strict.

Answer 2

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)

[Edit]

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)

• Hugo Sereno Ferreira: Very nice your one-liner! I'll award the +50... but could you also solve it with infinite lists (streams)?

Answer 3

 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
 else iter(acc :+ rest.head, met + rest.head, rest.tail)
 }
 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.