CODEWITHSUNDEEP
listscaladictionaryhigher-order-functions
sc_ray
sc_ray

Reputation: 8043

Converting List[Option[A]] to Option[List[A]] using Map instead of FlatMap

In the book Functional Programming in Scala there is a question that asks to convert a List of Options into an Option of Lists. The function signature is as follows:

def sequence[A](a:List[Option[A]]):Option[List[A]]

On the book's website, this function is implemented as follows:

def sequence[A](a:List[Option[A]]):Option[List[A]] = a match {
   case Nil => Some(Nil)
   case h::t => h flatMap (r => sequence(t) map (h::_))
}

I am a little confused by the h flatMap (r => sequence(t) map (h::_)) part. If I break it down, it goes as follows:

h is of type Option[A]. Performing flatMap on h would return an Option[B] but it takes as a parameter a function f that takes A as a parameter and return an Option[B], now in the example above, sequence(t) map (h :: _) would return an Option[List[A]] which aligns with the return type of the function.

Can map be used instead of flatMap to perform the transformation from List[Option[A]] to Option[List[A]]? Also, the solution provided doesn't seem to be tail-recursive. Can it be made tail-recursive?

Upvotes: 3

Views: 1756

Answers (3)

Josep Prat
Josep Prat

Reputation: 503

I found another way to implement the seq function that is not using recursion implicitely:

def seq[A](a: List[Option[A]]):Option[List[A]] = a.foldLeft(Some(Nil):Option[List[A]])((collected,elem) => elem.flatMap(el=> collected.map(el::_)))

Upvotes: 1

Jatin
Jatin

Reputation: 31724

h flatMap (r => sequence(t) map (h::_)) should be h flatMap (r => sequence(t) map (r::_)) as h is of type Option[A] and r is of type A. We are trying to append element to the list of type List[A] in the map and hence r::_.

Another solution without using recursion would be:

def sequence[A](a: List[Option[A]])(implicit nullValue: A):Option[List[A]] = {
 Option(a map { x => x.getOrElse(nullValue)})
}

Upvotes: 1

senia
senia

Reputation: 38045

There is a typo:

case h::t => h flatMap (r => sequence(t) map (h::_))

There should be r :: _, or h.toList ::: _, not h :: _

sequence(t) returns Option[List[A]]. map (r::_) on Option[List[A]] don't change the type. It just takes a List[A] from Option if any and prepends it with A.

So the type of sequence(t) map (r :: _) is Option[List[A]].

You don't need flatMap here:

def sequence[A](a:List[Option[A]]):Option[List[A]] = a match {
   case Nil => Some(Nil)
   case None :: _ => None
   case Some(r) :: t => sequence(t) map (r :: _)
}

The solution can be made tail-recursive. The common problem with tail-recursion and List is that you have to reverse you list in the end:

def sequence[A](a:List[Option[A]]):Option[List[A]] = {
  @tailrec def loop(a: List[Option[A]], subres: List[A] = Nil): Option[List[A]] =
    a match {
      case Nil => Some(subres)
      case None :: _ => None
      case Some(r) :: t => loop(t, r :: subres)
    }
  loop(a) map {_.reverse}
}

In fact it can be made not recursive at all:

def sequence[A](a:List[Option[A]]):Option[List[A]] =
  a.foldLeft(Option(List[A]())){ (os, oe) =>
    for {
      s <- os
      e <- oe
    } yield e :: s
  }.map{ _.reverse }

Upvotes: 4

Related Questions