Search code examples
scalafunctional-programmingtraversal

Implementing traverse function in one iteration in scala

It combines a list of Options into one Option containing a list of all the Some values in the original list. If the original list contains None even once, the result of the function should be None, otherwise the result should be Some with a list of all the values. The signature is

def sequence[A](a: List[Option[A]]): Option[List[A]]

I came up with the following solution

def sequence[A](l: List[Option[A]]): Option[List[A]] = {
  if (l.exists(_.isEmpty)) None
  else Some(l.map(_.get))
}

which does not seem to be perfect at all as it iterates the list and applies a f function twice to average 50% of elements.

Solution

  • Non-functional-style with fast fail:

    def sequence[A](xs: List[Option[A]]): Option[List[A]] = 
  Some(xs map (_.getOrElse(return None))) //this return (inside lambda) is implemented with exception in scala

    Recursive one:

    def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match {
  case Nil => None //or `Some(Nil)`
  case None :: tail => None
  case Some(head) :: Nil => Some(head :: Nil)
  case Some(head) :: tail => sequence(tail).map(head :: _) 
}

    Vector-based N (not 1.5*N) steps, but without fast fail:

    def sequence[A](xs: Vector[Option[A]]): Option[Vector[A]] = 
  Some(xs.flatten) filter (_.size == xs.size) //getting size is fast for vector

    Vector + view based with fast fail:

    //`view` doesn't create intermidiate collection and applies everything in one iteration
def sequence[A](xs: Vector[Option[A]]): Option[Seq[A]] = 
  Some(xs.view.takeWhile(_.nonEmpty).map(_.get).force) filter (_.size == xs.size)

    Anyway, only performance tests will tell you the true about effectiveness here. All these algorithms (including yours) are linear O(N) and it's the best complexity you can get anyway. So, further optimizations may not worth it.