如何使用函数式编程返回列表中的所有正数和第一个负数？

Question

想象一下,我有一个正面和负面的未排序列表.我想返回一个包含所有正整数和第一个负数的列表,但是然后忽略列表中的所有后续负数,同时保留排序.

我无法做到:

l = [1, 2, -4, 5, -6, -1, 3]
out = []
first = true
for n in l:
    if n >= 0:
        out.push(n)
    else if first:
        out.push(n)
        first = false

// out = [1, 2, -4, 5, 3]

我怎么能用Scala中的FP做到这一点？我在想(可能不会编译......):

val l = List(1, 2, -4, 5, -6, -1, 3)
val posl = l.map(_ >= 0)
val negl = l.zipWithIndex.map((n, i) => if (n < 0) (i, n) else (None, None)).head
// now split posl at negl._1, and create a new list of leftSlice :: negl._2 :: rightSlice?

这是正确的方法,还是有更优雅,简洁的方式？

Answer 1

如果没有稍微过于聪明的递归+模式匹配答案,那就不是一个合适的函数式编程问题.

def firstNegAllPos(l:List[Int]):List[Int] = {
   l match{
      case x::xs if x>=0 => x::firstNegAllPos(xs)
      case x::xs if x<0 => x::xs.filter(_>=0)
      case Nil => Nil
   }
}

Answer 2

如果您不介意保持一点状态,您可以一次性完成 - 请注意var neg:

var neg = false
list.filter { 
    case x if x > 0  => true
    case _ if !neg   => neg = true
}

Answer 3

这是一种尾递归方式.与mz的答案相比,它只迭代你的列表一次,与Dimas的答案相比,它不使用可变状态,所以它是纯粹的功能.

def firstNegAllPos(list: List[Int]) : List[Int] = {
  def loop(in: List[Int], out: List[Int], negfound: Boolean) : List [Int] = {
    in match {
      case Nil => out
      case head :: tail =>
        if (negfound)
          loop(tail, if (head < 0) out else head :: out, true)
        else
          loop(tail, head :: out, head < 0)
    }
  }
  loop(list, Nil, false)
}

firstNegAllPos(List(1, 2, -4, 5, -6, -1, 3)) // List(3, 5, -4, 2, 1)

编辑:

上述实现提供了相反的结果.为了保留订单,您可以执行以下操作:

def firstNegAllPos(list: List[Int]) : List[Int] = {
  def loop(in: List[Int], out: List[Int], negfound: Boolean) : List [Int] = {
    in match {
      case Nil => out
      case head :: tail =>
        if (negfound)
          loop(tail, if (head < 0) out else head :: out, true)
        else
          loop(tail, head :: out, head < 0)
    }
  }
  loop(list, Nil, false).reverse
}

firstNegAllPos(List(1, 2, -4, 5, -6, -1, 3)) // List(1, 2, -4, 5, 3)

Answer 4

需求的直接翻译非常清楚,在列表上进行一次传递,并且功能正常:

val l = List(1, 2, -4, 5, -6, -1, 3) 

// split into any initial positive numbers, and the rest of the list 
val (pos, firstneg) = l.span(_ >= 0)

// if there were no negative numbers, return the original list.
// otherwise, it's the initial positives, the first negative, and
// the positive numbers from the rest of the list.
if (firstNeg.isEmpty) l else pos:::List(firstneg.head):::firstneg.tail.filter(_>=0)
//> res0: List[Int] = List(1, 2, -4, 5, 3)

(List周围firstneg.head只是:::两边的对称)