Converting List[Option[A]] to an Option[List[A]] in Scala

Question

I am new to FP and Scala and am reading the book Functional Programming in Scala. One of the exercises in Chapter 4 asks us to write a function called sequence which would convert a List[Option[A]] to an Option[List[A]]. Here Option is a reimplementation of the Option provided by the Scala library. Here's the required code.

trait Option[+A] {
    /* Function to convert Option[A] to Option[B] using the function passed as an argument */
    def map[B](f: A => B): Option[B] = this match {
        case None => None
        case Some(v) => Some(f(v))
    }

    /* Function to get the value in `this` option object or return the default value provided. Here,
     * `B >: A` denotes that the data type `B` is either a super-type of `A` or is `A`
     */
    def getOrElse[B >: A](default: => B): B = this match {
        case None => default
        case Some(v) => v
    }

    /* Used to perform (nested) operations on `this` and aborts as soon as the first failure is
     * encountered by returning `None`
     */
    def flatMap[B](f: A => Option[B]): Option[B] = {
        map(f).getOrElse(None)
    }
}

case class Some[+A](get: A) extends Option[A]   // used when the return value is defined
case object None extends Option[Nothing]        // used when the return value is undefined

Now I tried a lot, but I had to look up the solution for writing sequence, which is,

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)                   // Or `None`. A design decision in my opinion
    case h :: t => h.flatMap(hh => sequence(t).map(hh :: _))
}

I just want to make sure I understood the solution correctly. So here are my questions.

1. Is my intuition about the return value for case Nil correct? Is it really a design decision or is one way better than the other?
2. For case h :: t, this is what I understood. We pass the value h firstly to the anonymous function in flatMap (as hh) which invokes sequence recursively. This recursive call of sequence returns an Option encapsulating the Options in t. We invoke map on this returned value and pass h to the anonymous function (as hh) which then creates a new List[A] with the list returned by the recursive call as the tail and h as the head. This value is then encapsulated in Option by invoking Some and returned.

Is my understanding for the the second part correct? If yes, is there a better way to explain it?

Answer 1

It seems that sequence is intended to return None if any element in the list is None, and return Some of values in the list otherwise. So your intuition about the Nil case is not correct -- Nil is an empty list that contains no Nones, so the result should not be None.

Let's take it one step at a time, from the inside out.

Suppose we have some variable optionListof type Option[List[A]] and some variable a of type A. What do we get when we call:

optionList.map(a :: _)

If optionList is None, then this will be None. If optionList contains a list, say list, this will be Some(a :: list).

Now if for some variable option of type Option[A], what do we get when we call:

option.flatMap(a => optionList.map(a :: _))

If option is None, then this will be None. If option contains a value, say a, then this will be optionList.map(a :: _), which we figured out above (by the definition of flatMap).

Now if we tie it together, we see that if any element is None, then the recursive call is avoided and the whole result will be None. If no element is None, then the recursive call will keep appending the element's values, and the result will be Some of the list's element's internal values.

It might be more clearer if you rewrite the inner part:

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)
    case h :: t => h match {
        case None => None
        case Some(head) => sequence(t) match {
            case None => None
            case Some(list) => Some(head :: list)
        }
    }
}

Or even less idiomatic, but maybe clarifying:

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)
    case h :: t => 
        val restOfList = sequence(t)
        if (h == None || restOfList == None) None else Some(h.get :: restOfList.get)
}

You could also rewrite this pretty naturally as a fold without recursion, in case that is what's confusion you:

def sequence[A](l: List[Option[A]]) = (Option(List.empty[A]) /: l) {
    case(Some(sofar), Some(value)) => Some(value :: sofar); 
    case(_, _) => None 
}

Answer 2

I think I was trying to solve same question from the same book and came up with this. It works for me and looks pretty clear and consice

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

    }

  }

}