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

7 Answers 7

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].

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

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)
    }
4
  • foldRight is equivalent to a reverse and fold left operation. So this traverses twice.
    – 2rs2ts
    Feb 24, 2015 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. Feb 25, 2015 at 3:47
  • For List it is implemented as reverse.foldLeft. See the source.
    – 2rs2ts
    Feb 26, 2015 at 2: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. Feb 26, 2015 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
1
  • 4
    You can use the existing isEmpty instead of defining isNone. Jul 19, 2011 at 18:03
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 :: _))
}
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)
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

Your Answer

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

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