3

在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 将返回 anOption[B]但它需要一个函数 f 作为参数，该函数将 A 作为参数并返回 an Option[B]，现在在上面的示例中，sequence(t) map (h :: _)将返回Option[List[A]]与函数的返回类型一致的 an。

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

4

3 回答 3

4

有一个错字：

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

应该有r :: _，或者h.toList ::: _，没有h :: _

sequence(t)返回Option[List[A]]。不要改变类型map (r::_)。Option[List[A]]如果有的话，它只需要一个List[A]fromOption并在它前面加上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 }
于 2013-06-24T06:15:57.150 回答
1

h flatMap (r => sequence(t) map (h::_))应该是h flatMap (r => sequence(t) map (r::_))as his of typeOption[A]和ris of type A。我们正在尝试将元素附加到List[A]地图中的类型列表中，因此r::_.

不使用递归的另一种解决方案是：

def sequence[A](a: List[Option[A]])(implicit nullValue: A):Option[List[A]] = {
 Option(a map { x => x.getOrElse(nullValue)})
}
于 2013-06-24T06:28:39.160 回答
1

我找到了另一种实现不使用递归的 seq 函数的方法：

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::_)))
于 2014-05-29T16:07:44.543 回答