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

它将Option的列表组合到一个Option中，其中包含原始列表中所有Some值的列表。如果原始列表甚至包含一次None，则函数的结果应该是None，否则结果应该是Some以及所有值的列表。签名是在scala中的一次迭代中实现遍历函数

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％。

来源

2015-08-09 zapadlo

非功能性风格的快速失败：

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-based N（not 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），它是你可以得到的最好的复杂度。所以，进一步的优化可能不值得。

来源

2015-08-09 10:31:48 dk14

这里有一个可能性：

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元素，它会很快停止评估名单。并且应该返回与实现相同的结果。但是，注意这个实现对于空输入列表将返回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)
或list :+ item更换item :: list。

虽然，list :+ item不追加项目的List的最佳方式。如果您想保留订单并使用'@tailrec'方法，我建议您使用Vector作为结果类型，而不是List。

来源

2015-08-09 09:16:28

您对结果缺少'.map（_。reverse）'。你也可以将两个'None'匹配情况合并为_ _> None，并将它们放在'Some'情况之后。 – Arjan

编辑我的答案与关于列表顺序的评论。然而，如果我申请你的第二个建议，我不得不放弃'@ tailrec'，would'nt I. –

不，要成为尾部递归，recusrive调用不必在最新的匹配语句中，只是该特定情况下的最后一项陈述。 – Arjan

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

来源

2015-08-09 09:43:25 Arjan

这里有一个快速和肮脏的解决方案，一定要得罪大家的良好的功能情面:)

import scala.util.Try 

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

来源

2015-08-09 09:56:28

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

回答

相关问题