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\$
1

3 Answers 3

Reset to default
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
\$\endgroup\$
4
  • \$\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\$ Commented Dec 28, 2011 at 17:41
  • \$\begingroup\$ Nevertheless, amazing display of your functional-fu! \$\endgroup\$ Commented Dec 28, 2011 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\$ Commented Dec 28, 2011 at 21:34
  • \$\begingroup\$ Thanks for the tip on scalaz. I was already wrapping my head on why foldRight was being strict. \$\endgroup\$ Commented Dec 29, 2011 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)
\$\endgroup\$
1
  • \$\begingroup\$ Very nice your one-liner! I'll award the +50... but could you also solve it with infinite lists (streams)? \$\endgroup\$ Commented Apr 2, 2012 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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.