1
\$\begingroup\$

Given:

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

  def lefts[A, B](xs: Seq[Either[A, B]]): Seq[A] =
    xs.flatMap {
      case Right(_) => List.empty
      case Left(x)  => 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> 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> val distinct = rights(xs).distinct
distinct: Seq[Int] = List(42, 6)

scala> combine(lefts(xs), distinct)
res1: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6))
\$\endgroup\$
1
\$\begingroup\$

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) => if (seen(x)) None else { seen += x; Some(Right(x)) }  
             case x => 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!).

\$\endgroup\$
0
\$\begingroup\$

If you don't care about maintaining the order of the elements in the original List, I'd just go with the built-in methods and not unwrap the values from the Either:

scala> 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> val (rights, lefts) = xs.partition(_.isRight)
rights: Seq[Either[String,Int]] = List(Right(42), Right(6), Right(42))
lefts: Seq[Either[String,Int]] = List(Left(foo))

scala> lefts ++ rights.distinct
res1: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6))

If maintaining order does matter, and assuming you'd want to keep the first occurrence, I'd go with a foldLeft:

scala> val xs2: Seq[Either[String, Int]] = Seq(Left("foo"), Right(42), Left("bar"), Right(6), Left("foo"), Right(42), Right(9))
xs2: Seq[Either[String,Int]] = List(Left(foo), Right(42), Left(bar), Right(6), Left(foo), Right(42), Right(9))

scala> val (result, _) = xs2.foldLeft((Seq.empty[Either[String, Int]], Set.empty[Int])) { 
  case ((res, seen), l @ Left(_)) =>
    (res :+ l, seen)
  case ((res, seen), r @ Right(value)) if seen.contains(value) =>
    (res, seen)
  case ((res, seen), r @ Right(value)) =>
   (res :+ r, seen + value)
}
result: Seq[Either[String,Int]] = List(Left(foo), Right(42), Left(bar), Right(6), Left(foo), Right(9))

This keeps track of two values in the iteration, the result Seq and a Set of seen Int values. On each iteration, we:

  • update the result if the current value is a Left.
  • use the current result if the current value is a Right we've already seen.
  • update the result and set of seen values if it's a Right we haven't already seen.

At the end the set of seen values is discarded through destructing the resulting tuple and only result is saved.

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