在scala中的一次迭代中实现遍历函数

Question

它将 Option 的列表合并为一个 Option，其中包含原始列表中所有 Some 值的列表。如果原始列表只包含一次 None，则函数的结果应该是 None，否则结果应该是 Some 以及所有值的列表。签名是

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

我想到了以下解决方案

def sequence[A](l: List[Option[A]]): Option[List[A]] = {
  if (l.exists(_.isEmpty)) None
  else Some(l.map(_.get))
}

这似乎并不完美，因为它迭代列表并应用 f 函数两次以平均 50% 的元素。

Answer 1

这是一种可能性：

import scala.annotation.tailrec

def sequence[A](a: List[Option[A]]): Option[List[A]] = {
  @tailrec
  def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = {
    if (remaining.isEmpty) {
      result
    } else {
      (remaining.head, result) match {
        case (Some(item), Some(list)) => seq(remaining.tail, Some(item :: list))
        case _ => None
      }    
    }
  }

  seq(a, Some(Nil))
}

它会在遇到第一个 None 元素时立即停止计算列表。并且应该 return 与您的实施结果相同。但是，重要的是要注意，对于空输入列表，此实现将return Some(Nil)。

实施可以缩短一点，具体取决于您对表现力和其他可读性标准的偏好：

def sequence[A](a: List[Option[A]]): Option[List[A]] = {
  @tailrec
  def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = {
      (remaining, result) match {
        case (Nil, _) => result
        case (Some(item) :: tail, Some(list)) => seq(tail, Some(item :: list))
        case _ => None
      }
  }

  seq(a, Some(Nil))
}

结果将 Some 倒序排列或 None。如果您想保留列表顺序，则必须

将 seq(a, Some(Nil)) 替换为 seq(a, Some(Nil)).map(_.reverse)
或将 item :: list 替换为 list :+ item。

不过，list :+ item 并不是将项目附加到 List 的最佳方式。如果您想保留顺序并使用“@tailrec”方法，我建议使用 Vector 作为结果类型而不是 List.

Answer 2

def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match {
    case x :: xs => // Get one element at a time (Opton[A])
        for {
            a <- x // unwrap the Option[A] to A
            as <- sequence(xs) // Unwrap the recursive result of Option[List[A]] into List[A]
        } yield a :: as // Merge the elements and warp in Option
    case _ => Some(Nil) // sequence of an empty list is Some(List())
}

println(sequence(List[Some[Int]]())) // Some(List())
println(sequence(List(Some(1), None, Some(3)))) // None
println(sequence(List(Some(1), Some(2), Some(3)))) // Some(List(1, 2, 3))

Answer 3

这是一个快速而肮脏的解决方案，肯定会冒犯每个人良好的功能敏感性:)

import scala.util.Try

def sequence[A](xs: List[Option[A]]): Option[List[A]] =
  Try(xs.map(_.get)).toOption

Answer 4

快速失败的非功能风格：

def sequence[A](xs: List[Option[A]]): Option[List[A]] = 
  Some(xs map (_.getOrElse(return None))) //this return (inside lambda) is implemented with exception in scala

递归一：

def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match {
  case Nil => None //or `Some(Nil)`
  case None :: tail => None
  case Some(head) :: Nil => Some(head :: Nil)
  case Some(head) :: tail => sequence(tail).map(head :: _) 
}

Vector-基于 N（不是 1.5*N）步，但没有快速失败：

def sequence[A](xs: Vector[Option[A]]): Option[Vector[A]] = 
  Some(xs.flatten) filter (_.size == xs.size) //getting size is fast for vector

Vector + view 基于快速失败：

//`view` doesn't create intermidiate collection and applies everything in one iteration
def sequence[A](xs: Vector[Option[A]]): Option[Seq[A]] = 
  Some(xs.view.takeWhile(_.nonEmpty).map(_.get).force) filter (_.size == xs.size)

无论如何，只有性能测试才能告诉您这里关于有效性的真实情况。所有这些算法（包括你的）都是线性 O(N) 的，这是你能得到的最好的复杂度。因此，进一步的优化可能不值得。

在scala中的一次迭代中实现遍历函数

Implementing traverse function in one iteration in scala

scala

functional-programming

traversal