Convert a List of Options to an Option of List using Scalaz

Question

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
  }
}}

Prefix

Answer 1

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))

Delftware

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. – Delftware

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. – Prefix

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] – Hassan

import scalaz._; import Scalaz._; List(some(1), some(2), some(3)).sequence. I get: Some(List(1,2,3)) – Delftware

Seth: This is odd. If you omit the return type, it works just fine. def lo2ol[T](lo: List[Option[T]]) = lo.sequence – Delftware

Don't use scalaz-core_2.8.0.Beta1-5.0.1-SNAPSHOT, use scalaz-core_2.8.0.Beta1-5.0.0-SNAPSHOT. The former was inadvertantly published. lampsvn.epfl.ch/trac/scala/ticket/3152 is the likely cause of the problem. – Lowrey

I was able to get it working by using a recent Scala nightly which includes the fix for bug 3152. Thanks guys. – Hassan

@Apocalisp: will this also work on List[scala.concurrent.Future[T]]? – Primaveras

@ErikAllik Yes it will. – Delftware

@Apocalisp: did you mean Scalaz' Future? I'm getting could not find implicit value for parameter G: scalaz.Applicative[G]. – Primaveras

You will need an Applicative[scala.concurrent.Future] – Delftware

Answer 2

For some reason you dislike

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

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

Deceit

Not bad, but it goes over the list twice. – Delftware

@Apocalisp: Indeed, but that's almost always cheaper than making half of a new list before discarding it all and throwing back None. – Deceit

wouldn't if (lo contains None) None else Some(lo.flatten) be even shorter? – Primaveras

@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. – Deceit

@RexKerr: I was too lazy to keep thinking but I knew there was something sub-optimal about that flatten. – Primaveras

Answer 3

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))

Elegancy

Answer 4

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

Lowrey

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. – Prefix

@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. – Hassan

My bad, I mis-intperpreted the question. MA#foldMapDefault and MA#sequence both use Traverse[List], but using a different Applicative Functors. – Lowrey

Answer 5

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

    }
  }

}

Mirella