list - 使用 Map 而不是 FlatMap 将 List[Option[A]] 转换为 Option[List[A]]

Question

在书中Functional Programming in Scala有一个问题要求将选项列表转换为列表选项。函数签名如下:

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

在本书的网站上，这个功能是这样实现的:

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::_))
}

h flatMap (r => sequence(t) map (h::_)) 部分让我有些困惑。如果我分解它，它会如下所示:

h 的类型为 Option[A]。对 h 执行 flatMap 会返回一个 Option[B] 但它以一个函数 f 作为参数，该函数 f 以 A 作为参数并返回一个 Option[B]，现在在在上面的示例中，sequence(t) map (h::_) 将返回一个 Option[List[A]]，它与函数的返回类型一致。

是否可以使用 map 代替 flatMap 来执行从 List[Option[A]] 到 Option[List[A]] 的转换？此外，提供的解决方案似乎不是尾递归的。可以尾递归吗？

Answer 1

有一个错字:

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

应该有r::_，或者h.toList::::_，而不是h::_

sequence(t) 返回 Option[List[A]]。 map (r::_) on Option[List[A]] 不要改变类型。如果有的话，它只是从 Option 中获取一个 List[A]，并在它前面加上 A。

所以 sequence(t) map (r::_) 的类型是 Option[List[A]]。

这里不需要flatMap:

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 :: _)
}

可以使解决方案成为尾递归的。尾递归和 List 的常见问题是你必须在最后反转你的列表:

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

事实上它可以完全不递归:

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 }