删除给定列表的给定数量的正项

Question

假设我需要一个函数 List[Int] => Option[List[Int]] 来准确删除给定列表的 n 个元素 当且仅当 所有元素 > 0 .如果列表大小 <= n 函数应该 return None.

例如：

def posn(n: Int): List[Int] => Option[List[Int]] = ???
val pos4: List[Int] => Option[List[Int]] = posn(4)

scala> pos4(Nil)
res18: Option[List[Int]] = None

scala> pos4(List(-1))
res19: Option[List[Int]] = None

scala> pos4(List(-1, 2, 3))
res20: Option[List[Int]] = None

scala> pos4(List(1, 2, 3))
res21: Option[List[Int]] = None

scala> pos4(List(1, 2, 3, 4, 5))
res22: Option[List[Int]] = Some(List(5))

scala> pos4(List(1, 2, 3, -4, 5))
res23: Option[List[Int]] = None

我这样写posn:

def posn(n: Int): List[Int] => Option[List[Int]] = xs => 
  if (xs.size >= n && xs.take(n).forall(_ > 0)) Some(xs.drop(n)) else None

这个函数似乎有点工作，但似乎并不优雅和惯用。你会如何重写它？

Answer 1

这是一个（可以说）更惯用的实现，它使用模式匹配和对 posn 的递归调用 - 但我不确定它比您建议的实现更可取：

def posn(n: Int): List[Int] => Option[List[Int]] = xs => (n, xs) match {
  case (0, _) => Some(xs) // stop if enough objects dropped
  case (_, head :: tail) if head > 0 => posn(n - 1)(tail) // drop positive and move on
  case _ => None // found a negative item or end of xs => "fail"
}

Answer 2

我不知道是否有惯用的或优雅的方法来做到这一点。似乎没有可以从你的逻辑中提取的通用模式，除了你已经完成的（使用 drop 和 take），所以我不相信你会找到一些更有用的预定义方法

但是，您遍历了几次列表，这是可以避免的：

def posn(n: Int): List[Int] => Option[List[Int]] = xs => {
  val (head, tail) = xs.splitAt(n) //does take and drop in one run
  if (head.lengthCompare(n) == 0 && head.forall(_ > 0)) Some(tail) // lengthCompare does not compute the whole length if there is no need to
  else None 
}

这仍然不完美，比你的版本更冗长。

您也可以使用尾递归一次完成所有操作（这里假设 n>=0）：

def posn(n: Int): List[Int] => Option[List[Int]] = xs =>
  if (n == 0) Some(xs) 
  else if (xs.isEmpty || xs.head <= 0) None
  else posn(n - 1)(xs.tail)

如果天真地实施 List 会更有效率，但我真的怀疑您是否会看到任何改进。

Answer 3

我会写一个通用版本并用它来定义 posn:

def dropWhen[T](n: Int, p: T => Boolean, l: List[T]): Option[List[T]] = {
    val (f, s) = l.splitAt(n)
    if (f.length >= n && f.forall(p)) { Some(s) } else { None }
}

def posn(n: Int): List[Int] => Option[List[Int]] = l => dropWhen(n, (i : Int) => i > 0, l)

注意这个方法扫描长度为n的前缀两次

Answer 4

另一种（非递归）替代方法：使用 zipWithIndex 和 dropWhile 删除前 N 个正数，然后检查 head 以查看第一个剩余项是否恰好在位置 n：如果是，我们就得到了我们想要的，否则我们可以 return None:

def posn(n: Int): List[Int] => Option[List[Int]] = xs =>
  Some(xs.zipWithIndex.dropWhile { case (v, i) => v > 0 && i < n })
    .find(_.headOption.exists(_._2 == n)) // first index should be n 
    .map(_.map(_._1)) // remove indices

删除给定列表的给定数量的正项

Drop a given number of positive items of a given list

scala

list

scala-collections