Implementing move function in one iteration in scala
It concatenates the list Option
into one Option
containing a list of all the values Some
in the original list. If the original list contains None
exactly one time, the result of the function must be None
, otherwise the result must be Some
with a list of all values. Signature
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 doesn't seem absolutely perfect as it iterates over the list and applies the function twice f
to average 50% of the elements.
source to share
Non-functional fast crashing style:
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:
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 on N
(not 1.5 * N) steps, but without fast crashing:
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 on fast crash:
//`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)
In any case, only performance tests will tell you the performance here. All of these algorithms (including yours) are linear O (N) and this is the best complexity you can get anyway. So further optimization may not be worth it.
source to share
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 element None
. And should return the same result as your implementation. It is important to note , however, that this implementation will return Some (Nil) for an empty input list.
The implementation can be shortened slightly, depending on your preference for 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 be Some
in reverse order or None
. If you want to keep the order of the list, you need
- replace
seq(a, Some(Nil))
withseq(a, Some(Nil)).map(_.reverse)
- or replace
item :: list
withlist :+ item
.
Although list :+ item
not the optimal way to add items to List
. If you want to keep the order and use the "@tailrec" approach, I would recommend using the result type Vector
instead List
.
source to share
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))
source to share