Converting the [Option [A]] list to the [List [A]] option in Scala

Question

I am new to FP and Scala and reading the book Functional Programming in Scala. In one of the exercises in chapter 4, we asked for a function called sequence that converts List[Option[A]] to Option[List[A]] . Here, Option is a reimplementation of Option provided by the Scala library. Code is required here.

 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 for a solution for writing a 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 understand the solution correctly. So here are my questions.

• Is my intuition regarding the return value for case Nil correct? Is this really a design decision or is one of the methods better than the other?
• For case h :: t this is what I understood. First, we pass the value of h an anonymous function in flatMap (like hh ), which calls a recursive sequence . This recursive call to sequence returns an Option encapsulating Option at t . We call map on this return value and pass h an anonymous function (like hh ), which then creates a new List[A] with the list returned by the recursive call, like tail and h as the header. This value is then encapsulated in Option by calling Some and return.

Do I understand correctly that the second part is correct? If so, is there a better way to explain this?

Answer 1

It seems that sequence intended to return None if any element in the list is None and returns Some values ​​in the list otherwise. So your intuition about the Nil case is incorrect - Nil is an empty list that does not contain None s, so the result should not be None .

Let me do it step by step, from the inside.

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

 optionList.map(a :: _) 

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

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

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

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

Now, if we bind 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 item is None , then the recursive call will continue to add item values, and the result will be Some internal values ​​of the list item.

It may be clearer if you rewrite the inside:

 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 perhaps more precise:

 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 can also rewrite this quite naturally as fold without recursion, in case this confuses 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 tried to solve the same question from the same book and came up with this. It works for me and looks pretty clear and straightforward.

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

Answer 3

If you want to convert List [Option [T]] to List [T], just flatten it to fill the other side, which is None for the empty list, and Some for the non-empty list just uses pattern matching.

  val list = List(Some("a"), Some("b"), None, Some("c")) list.flatten match { case Nil => None case l => Some(l) }