Applying Function to `Seq[B]` in `Seq[Either[A, B]]` Given:

  def rights[A, B](xs: Seq[Either[A, B]]): Seq[B] =
    xs.flatMap {
      case Right(x) =&gt; List(x)
      case Left(_)  =&gt; List.empty
    }

  def lefts[A, B](xs: Seq[Either[A, B]]): Seq[A] =
    xs.flatMap {
      case Right(_) =&gt; List.empty
      case Left(x)  =&gt; List(x)
    }

  def combine[A, B](xs: Seq[A], ys: Seq[B]): Seq[Either[A,B]] = {
    val l: Seq[Either[A, B]] = xs.map(Left[A,B](_))
    val r: Seq[Either[A, B]] = ys.map(Right[A,B](_))
    l ++ r
  }


Is there a better way to do the following, i.e. apply distinct to the Right[Int] in the Seq[Either[String, Int]].

Look to res1 in the below output as the desired output.

scala&gt; val xs: Seq[Either[String, Int]] = List( Left("foo"), Right(42), Right(6), Right(42) )
xs: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6), Right(42))

scala&gt; val distinct = rights(xs).distinct
distinct: Seq[Int] = List(42, 6)

scala&gt; combine(lefts(xs), distinct)
res1: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6))
The problem with @hayden.sikh's answer (the one that preserves order) is that it has a suboptimal complexity, and is especially inefficient if the Seq is a List (which it is in your REPL session). Appending an element to a list with :+ has linear complexity. Calling contains on a sequence too. So this is O(n^2).

It would be easy to adapt the answer by using a Set in the foldLeft accumulator, appending with +: and reversing the list at the end.
Or, to avoid the complexity and the cost of maintaining an immutable Set, simply use a mutable one and a flatMap:

val seen = mutable.HashSet[Int]()
xs flatMap { case Right(x) =&gt; if (seen(x)) None else { seen += x; Some(Right(x)) }  
             case x =&gt; Some(x) }


Mutability is fine as long as it's kept local, for example as a detail in an algorithm's implementation (most of the algorithms of the Scala standard library use mutability too, including distinct!).