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

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\$ Dec 28, 2011 at 17:41
  • \$\begingroup\$ Nevertheless, amazing display of your functional-fu! \$\endgroup\$ 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\$ 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\$ 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\$ 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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