15

What is the equivalent of Haskell's sequence in Scala? I want to turn list of options into an option of list. It should come out as None if any of the options is None.

List(Some(1), None, Some(2)).???     --> None
List(Some(1), Some(2), Some(3)).???  --> Some(List(1, 2, 3))
Chris Frederick
  • 5,482
  • 3
  • 36
  • 44
luntain
  • 4,560
  • 6
  • 37
  • 48
  • why don't you ask the question in a way that will make it understabable to people not familiar with haskell? – Kim Stebel Jul 19 '11 at 16:30
  • 2
    Possible duplicate: http://stackoverflow.com/questions/4730842/how-to-transform-scala-collection-of-optionx-to-collection-of-x – kiritsuku Jul 19 '11 at 16:33
  • 4
    I disagree that it's a duplicate of http://stackoverflow.com/questions/4730842/how-to-transform-scala-collection-of-optionx-to-collection-of-x. Technically, the second part of [this answer](http://stackoverflow.com/questions/4730842/how-to-transform-scala-collection-of-optionx-to-collection-of-x/4732682#4732682) contains the answer to this question, but the two original questions are asking for different things. – overthink Jul 19 '11 at 18:05
  • quasi-duplicate of http://stackoverflow.com/questions/2569014/convert-a-list-of-options-to-an-option-of-list-using-scalaz – Erik Kaplun Mar 30 '14 at 03:08

7 Answers7

24

Scalaz defines sequence.

Here's an example:

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> List(Some(1), None, Some(2)).sequence
res0: Option[List[Int]] = None

scala> List(some(1), some(2), some(3)).sequence
res1: Option[List[Int]] = Some(List(1, 2, 3))

Note that in the second example, you have to use Scalaz's some function to create a Some -- otherwise, the List is constructed as List[Some[Int]], which results in this error:

scala> List(Some(1), Some(2), Some(3)).sequence
<console>:14: error: could not find implicit value for parameter n: scalaz.Applicative[N]
       List(Some(1), Some(2), Some(3)).sequence

The Scalaz some(a) and none functions create Some and None values of type Option[A].

mpilquist
  • 3,855
  • 21
  • 22
17

If you want a solution for just List and Option rather a general monad then following will do the job,

def sequence[T](l : List[Option[T]]) = 
  if (l.contains(None)) None else Some(l.flatten)

REPL session,

scala> sequence(List(Some(1), None, Some(2)))
res2: Option[List[Int]] = None

scala> sequence(List(Some(1), Some(2), Some(3)))
res3: Option[List[Int]] = Some(List(1, 2, 3))

Update 20/8/2014

Just use Scalaz ...

Miles Sabin
  • 23,015
  • 6
  • 61
  • 95
4

Here is the same function as above using a combination of foldRight and map/ flatmap that only has to traverse the list once:

  def sequence[A](lo: List[Option[A]]): Option[List[A]] = 
    lo.foldRight (Option(List[A]())) { (opt, ol) => 
      ol flatMap (l => opt map (o => o::l))
    }

Or, if you prefer the for comprehension version:

  def sequence2[A](lo: List[Option[A]]): Option[List[A]] = 
    lo.foldRight (Option(List[A]())) { (opt, ol) =>
      for {l <- ol; o <- opt} yield (o::l)
    }
Garrett Rowe
  • 1,205
  • 9
  • 13
  • `foldRight` is equivalent to a reverse and fold left operation. So this traverses twice. – 2rs2ts Feb 24 '15 at 19:34
  • That may be one way to implement foldRight, but that is not how it is currently implemented in Scala. If it were then foldRight wouldn't blow the stack on large inputs. As it is currently implemented, foldRight will only traverse once. – Garrett Rowe Feb 25 '15 at 03:47
  • For `List` it is implemented as `reverse.foldLeft`. See [the source](https://github.com/scala/scala/blob/b07fab89e96ff9ce601fe00f8ce28de1df2d001b/src/library/scala/collection/immutable/List.scala#L396-L397). – 2rs2ts Feb 26 '15 at 02:15
  • 1
    You're right. My understanding was out of date. Although when the answer was originally written, that was not the case. Looks like it changed [in 2013](https://github.com/scala/scala/commit/6db4db93a7d976f1a3b99f8f1bffff23a1ae3924). – Garrett Rowe Feb 26 '15 at 23:39
2

First off, I recommend that you check out the API docs for List.

As for a solution, this may not be the most graceful way to do it, but it'll work (and with no external dependencies):

// a function that checks if an option is a None
def isNone(opt:Option[_]) = opt match {
  case None => true
  case _ => false
}

//templated for type T so you can use whatever Options
def optionifyList[T](list:List[Option[T]]) = list.exists(isNone) match {
  case true => None
  case false => Some(list.flatten)
}

And a test just to be sure...

scala> val hasNone = Some(1) :: None :: Some(2) :: Nil
hasNone: List[Option[Int]] = List(Some(1), None, Some(2))

scala> val hasSome = Some(1) :: Some(2) :: Some(3) :: Nil
hasSome: List[Some[Int]] = List(Some(1), Some(2), Some(3))

scala> optionifyList(hasSome)
res2: Option[List[Int]] = Some(List(1, 2, 3))

scala> optionifyList(hasNone)
res3: Option[List[Int]] = None
Dylan
  • 13,645
  • 3
  • 40
  • 67
1

Maybe this helps, as it traverses once only and use recursion

def sequence[A](a: List[Option[A]]): Option[List[A]] =
a match {
  case Nil => Some(Nil)
  case h :: rest => h.flatMap(x => sequence(rest).map(x :: _))
}
jbi
  • 11
  • 1
0

This is very simple with a for comprehension:

val x : Option[String] = Option("x")
val y : Option[String] = Option("y")
val z : Option[String] = None

// Result -> a: Option[List[String]] = None    
val a = for {
  x <- x
  y <- y
  z <- z
} yield List(x,y,z)    

// Result -> b: Option[List[String]] = Some(List(x, y))    
val b = for {
  x <- x
  y <- y
} yield List(x,y)
mixja
  • 6,977
  • 3
  • 32
  • 34
0

Since you need to flatten anyway, just do it first...

def sequence(lo: List[Option[A]]): Option[List[A]] = lo.flatten match {
    la: List[A] if(la.length == lo.length) => Some(la)
    _ => None
}

tail recursion might be quickest

jayflo
  • 1,105
  • 1
  • 12
  • 21