current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|improve this question
1  
You probably just want the distinct method... see stackoverflow.com/questions/1538598/… –  Nicolas Payette Dec 28 '11 at 2:31

3 Answers 3

up vote 4 down vote

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
share|improve this answer
    
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
up vote 3 down vote
+25
 
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)
share|improve this answer
    
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
up vote 1 down vote 
    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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.