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

scala

Solution

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 `None`s, 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 `optionList`of 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 
}

Problem

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. - 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? - 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 `Option`s 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?

Original source