CODEWITHSUNDEEP
scala
aa8y
aa8y

Reputation: 3942

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

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?

Upvotes: 15

Views: 8130

Answers (6)

Nathan Brown
Nathan Brown

Reputation: 1203

Taking inspiration from Future.sequence which ostensibly does the same transformation for an IterableOnce of Futures, here is an adapted implementation for Options.

This also has the benefit of using implicit collection builders, meaning that it is collection type independent.

final def sequence[A, CC[X] <: IterableOnce[X], To](in: CC[Option[A]])(implicit bf: BuildFrom[CC[Option[A]], A, To]): Option[To] = {
  in.iterator
    .foldLeft(Option(bf.newBuilder(in))) {
      (b, a) => {
        b.flatMap(builder => a.map(builder.addOne))
      }
    }
    .map(_.result())
}

The only negative of this implementation is that it will not exit on the first None encountered but instead traverse the whole iteration.

Upvotes: 0

jq170727
jq170727

Reputation: 14625

Assuming l is a List[Option[A]] here is another approach using partition and isEmpty. 

l.partition(_.isEmpty) match {
  case (Nil, x) => Some(x.map(_.get))
  case _        => None
}

Note that when given an empty list it will return Some(List()). If None is desired adding another case is straightforward:

l.partition(_.isEmpty) match {
  case (Nil, Nil) => None
  case (Nil, x)   => Some(x.map(_.get))
  case _          => None
}

Upvotes: 0

vantony
vantony

Reputation: 513

Converting List[Option[A]] to Option[List[A]] using foldLeft:

def optionSequence[A](loa: List[Option[A]]): Option[List[A]] =
    loa
      .foldLeft(Option(List.empty[A]))((ol, v) =>
          (ol, v) match {
          case (None, _) | (_, None) => None
          case (Some(l), Some(av))   => Some(av :: l)
      })
      .map(_.reverse)

Since List is a linked list, prepending is faster than appending. This is why I am prepending the values to the final list and then reversing the list (using the map) to preserve the ordering.

Upvotes: 0

Shankar Shastri
Shankar Shastri

Reputation: 1154

Tail-Recursive Solution

def seqToOption[T](s: Seq[Option[T]]): Option[Seq[T]] = {
  @tailrec
  def seqToOptionHelper(s: Seq[Option[T]], accum: Seq[T] = Seq[T]()): Option[Seq[T]] = {
    s match {
      case Some(head) :: Nil => Option(head +: accum)
      case Some(head) :: tail => seqToOptionHelper(tail, head +: accum)
      case _ => None
    }
  }
  seqToOptionHelper(s)
}

Original answer: Need to convert Seq[Option[A]] to Option[Seq[A]]

Upvotes: 0

Dmitri
Dmitri

Reputation: 36280

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

    }

  }

}

Upvotes: 1

Ben Reich
Ben Reich

Reputation: 16324

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 
}

Upvotes: 5

Related Questions