29

I want to transform a List[Option[T]] into a Option[List[T]]. The signature type of the function is

def lo2ol[T](lo: List[Option[T]]): Option[List[T]]

The expected behavior is to map a list that contains only Somes into a Some containing a list of the elements inside the elements Some's. On the other hand, if the input list has at least one None, the expected behavior is to just return None. For example:

scala> lo2ol(Some(1) :: Some(2) :: Nil)
res10: Option[List[Int]] = Some(List(1, 2))

scala> lo2ol(Some(1) :: None :: Some(2) :: Nil)
res11: Option[List[Int]] = None

scala> lo2ol(Nil : List[Option[Int]])
res12: Option[List[Int]] = Some(List())

An example implementation, without scalaz, would be:

def lo2ol[T](lo: List[Option[T]]): Option[List[T]] = {
  lo.foldRight[Option[List[T]]](Some(Nil)){(o, ol) => (o, ol) match {
    case (Some(x), Some(xs)) => Some(x :: xs);
    case _ => None : Option[List[T]]; 
}}}

I remember seeing somewhere a similar example, but using Scalaz to simplify the code. How would it look like?


A slightly more succinct version, using Scala2.8 PartialFunction.condOpt, but still without Scalaz:

import PartialFunction._

def lo2ol[T](lo: List[Option[T]]): Option[List[T]] = {
  lo.foldRight[Option[List[T]]](Some(Nil)){(o, ol) => condOpt(o, ol) {
    case (Some(x), Some(xs)) => x :: xs
  }
}}

5 Answers 5

23

There's a function that turns a List[Option[A]] into an Option[List[A]] in Scalaz. It's sequence. To get None in case any of the elements are None and a Some[List[A]] in case all the elements are Some, you can just do this:

import scalaz.syntax.traverse._
import scalaz.std.list._     
import scalaz.std.option._

lo.sequence

This method actually turns F[G[A] into G[F[A]] given that there exists an implementation of Traverse[F], and of Applicative[G] (Option and List happen to satisfy both and are provided by those imports).

The semantics of Applicative[Option] are such that if any of the elements of a List of Options are None, then the sequence will be None as well. If you want to get a list of all the Some values regardless of whether any other values are None, you can do this:

lo flatMap (_.toList)

You can generalize that for any Monad that also forms a Monoid (List happens to be one of these):

import scalaz.syntax.monad._

def somes[F[_],A](x: F[Option[A]])
                 (implicit m: Monad[F], z: Monoid[F[A]]) =
  x flatMap (o => o.fold(_.pure[F])(z.zero))
11
  • 1
    But if you want just the Some values of the List[Option[A]], you don't need Option anymore. You'll have either an empty list or a nonempty list of A.
    – Apocalisp
    Commented Apr 3, 2010 at 15:10
  • Actually, I do want to get None in case any of the elements are None, so sequence is exactly what I asked for. I'll try to edit the question to clarify the requirement. Commented Apr 3, 2010 at 16:20
  • I can't get lo.sequence to work. Using scala-2.8.0.Beta1 and scalaz-core_2.8.0.Beta1-5.0.1-SNAPSHOT.jar, if I enter def lo2ol[T](lo: List[Option[T]]): Option[List[T]] = lo.sequence, I get <console>:10: error: diverging implicit expansion for type scalaz.Applicative[N]
    – Seth Tisue
    Commented Apr 4, 2010 at 20:54
  • import scalaz._; import Scalaz._; List(some(1), some(2), some(3)).sequence. I get: Some(List(1,2,3))
    – Apocalisp
    Commented Apr 5, 2010 at 3:55
  • Seth: This is odd. If you omit the return type, it works just fine. def lo2ol[T](lo: List[Option[T]]) = lo.sequence
    – Apocalisp
    Commented Apr 5, 2010 at 4:01
20

For some reason you dislike

if (lo.exists(_ isEmpty)) None else Some(lo.map(_.get))

? That's probably the shortest in Scala without Scalaz.

5
  • 3
    Not bad, but it goes over the list twice.
    – Apocalisp
    Commented Apr 3, 2010 at 15:19
  • 3
    @Apocalisp: Indeed, but that's almost always cheaper than making half of a new list before discarding it all and throwing back None.
    – Rex Kerr
    Commented Apr 3, 2010 at 16:14
  • 9
    wouldn't if (lo contains None) None else Some(lo.flatten) be even shorter? Commented Mar 30, 2014 at 3:01
  • @ErikAllik - Yes, slightly, though I'd avoid flatten because you convert the Option to a List along the way. Good call on the contains, though.
    – Rex Kerr
    Commented Mar 30, 2014 at 4:19
  • 1
    @RexKerr: I was too lazy to keep thinking but I knew there was something sub-optimal about that flatten. Commented Mar 30, 2014 at 4:24
4

Starting Scala 2.13, and the addition of the Option::unless builder to the standard library, a variant to Rex Kerr's answer would be:

Option.unless(list contains None)(list.flatten)
// val list = List(Some(1), Some(2))          =>    Some(List(1, 2))
// val list = List(Some(1), None, Some(2))    =>    None

or, if performance is at stake (in order to avoid flatten's implicit conversion from Option to List):

Option.unless(list contains None)(list.map(_.get))
2

While the Applicative[Option] in Scalaz has the wrong behaviour to directly use MA#sequence, you can also derive an Applicative from a Monoid. This is made convenient with MA#foldMapDefault or MA#collapse.

In this case, we use a Monoid[Option[List[Int]]. We first perform an inner map (MA#∘∘) to wrap the individual Ints in Lists of one element.

(List(some(1), none[Int], some(2)) ∘∘ {(i: Int) => List(i)}).collapse assert_≟ some(List(1, 2))
(List(none[Int]) ∘∘ {(i: Int) => List(i)}).collapse                   assert_≟ none[List[Int]]
(List[Option[Int]]() ∘∘ {(i: Int) => List(i)}).collapse               assert_≟ none[List[Int]]

Abstracting from List to any container with instances for Traverse, Pointed and Monoid:

def co2oc[C[_], A](cs: C[Option[A]])
                  (implicit ct: Traverse[C], cp: Pointed[C], cam: Monoid[C[A]]): Option[C[A]] =
  (cs ∘∘ {(_: A).pure[C]}).collapse


co2oc(List(some(1), none[Int], some(2)))   assert_≟ some(List(1, 2))
co2oc(Stream(some(1), none[Int], some(2))) assert_≟ some(Stream(1, 2))
co2oc(List(none[Int]))                     assert_≟ none[List[Int]]
co2oc(List[Option[Int]]())                 assert_≟ none[List[Int]]

Sadly, trying to compile this code currently either triggers #2741 or sends the compiler into an infinite loop.

UPDATE To avoid traversing the list twice, I should have used foldMapDefault:

(List(some(1), none[Int], some(2)) foldMapDefault (_ ∘ ((_: Int).pure[List])))

This answer was based on the original request that an empty list, or a list containing only Nones, should return a None. Incidentally, this would be best modeled by the type Option[scalaz.NonEmptyList] -- NonEmptyList guarantees at least one element.

If you just want the a List[Int], there are many easier ways, given in other answers. Two direct ways that haven't been mentioned:

list collect { case Some(x) => x }
list flatten
3
  • The real use-case behind this question is perfectly fulfilled by the sequence method in Apocalisp's answer, including the result when given an empty list (which may happen in said use case). But thanks for mentioning the NEL type, it looks handy. Commented Apr 4, 2010 at 19:41
  • @retronym: Rafael wrote "if the input list has at least one None, the expected behavior is to just return None". Where as you wrote "a list containing only Nones, should return a None". That's very different. "list flatten" doesn't do what Rafael actually asked for.
    – Seth Tisue
    Commented Apr 4, 2010 at 20:48
  • My bad, I mis-intperpreted the question. MA#foldMapDefault and MA#sequence both use Traverse[List], but using a different Applicative Functors.
    – retronym
    Commented Apr 5, 2010 at 10:22
1

This worked for me. I hope this is a correct solution.

It returns None if one of the Options in the List is None, otherwise it returns Option of List[A]

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

  a.foldLeft(Option(List[A]())) {
    (prev, cur) => {

      for {
        p <- prev if prev != None
        x <- cur
      } yield x :: p

    }
  }

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.