5
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Hugo Sereno Ferreira Dec 28 '11 at 17:41
  • \$\begingroup\$ Nevertheless, amazing display of your functional-fu! \$\endgroup\$ – Hugo Sereno Ferreira Dec 28 '11 at 18:18
  • \$\begingroup\$ @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. \$\endgroup\$ – Daniel C. Sobral Dec 28 '11 at 21:34
  • \$\begingroup\$ Thanks for the tip on scalaz. I was already wrapping my head on why foldRight was being strict. \$\endgroup\$ – Hugo Sereno Ferreira Dec 29 '11 at 1:37
4
+25
\$\begingroup\$
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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very nice your one-liner! I'll award the +50... but could you also solve it with infinite lists (streams)? \$\endgroup\$ – Hugo Sereno Ferreira Apr 2 '12 at 15:35
1
\$\begingroup\$
    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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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