CODEWITHSUNDEEP
scalafunctional-programmingtraversal
Vadim Samokhin
Vadim Samokhin

Reputation: 3446

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.

Upvotes: 3

Views: 1080

Answers (4)

dk14
dk14

Reputation: 22374

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.

Upvotes: 2

Sascha Kolberg
Sascha Kolberg

Reputation: 7152

Here's one possibility:

import scala.annotation.tailrec

def sequence[A](a: List[Option[A]]): Option[List[A]] = {
  @tailrec
  def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = {
    if (remaining.isEmpty) {
      result
    } else {
      (remaining.head, result) match {
        case (Some(item), Some(list)) => seq(remaining.tail, Some(item :: list))
        case _ => None
      }    
    }
  }

  seq(a, Some(Nil))
}

It will stop evaluating the list as soon as it hits the first None element. And should return the same result as your implementation. However, it is important to note that this implementation will return Some(Nil) for an empty input list.

The implementation can be shortened a bit, depending on your preferences about expressiveness and other readability criteria:

def sequence[A](a: List[Option[A]]): Option[List[A]] = {
  @tailrec
  def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = {
      (remaining, result) match {
        case (Nil, _) => result
        case (Some(item) :: tail, Some(list)) => seq(tail, Some(item :: list))
        case _ => None
      }
  }

  seq(a, Some(Nil))
}

The result will Some list in reverse order or None. If you want to preserve the list order you will have to

  1. replace seq(a, Some(Nil)) with seq(a, Some(Nil)).map(_.reverse)
  2. or replace item :: list with list :+ item.

Though, list :+ item is not the optimal way to append items to a List. If you want to preserve the order and use a '@tailrec' approach I would recommend to use a Vector as result type instead of a List.

Upvotes: 3

Chris Martin
Chris Martin

Reputation: 30736

Here's a quick and dirty solution that is sure to offend everyone's good functional sensibilities :)

import scala.util.Try

def sequence[A](xs: List[Option[A]]): Option[List[A]] =
  Try(xs.map(_.get)).toOption

Upvotes: 5

Arjan
Arjan

Reputation: 21465

def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match {
    case x :: xs => // Get one element at a time (Opton[A])
        for {
            a <- x // unwrap the Option[A] to A
            as <- sequence(xs) // Unwrap the recursive result of Option[List[A]] into List[A]
        } yield a :: as // Merge the elements and warp in Option
    case _ => Some(Nil) // sequence of an empty list is Some(List())
}

println(sequence(List[Some[Int]]())) // Some(List())
println(sequence(List(Some(1), None, Some(3)))) // None
println(sequence(List(Some(1), Some(2), Some(3)))) // Some(List(1, 2, 3))

Upvotes: 1

Related Questions