在书中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]]
的转换?此外,提供的解决方案似乎不是尾递归的。可以尾递归吗?
最佳答案
有一个错字:
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 }
关于list - 使用 Map 而不是 FlatMap 将 List[Option[A]] 转换为 Option[List[A]],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17268334/