How to return all positives and the first negative number in a list using functional programming?

Question

Imagine I have an unsorted list of positive & negative ints. I want to return a list containing all the positive ints, and the first negative number, but then ignore all subsequent negative numbers from the list, while preserving the ordering.

Imperatively I could do:

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]

How could I do this with FP in Scala? I was thinking (probably won't compile...):

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?

Is this the right approach, or is there a more elegant, succinct way?

Answer 1

Here is an improvement on the most concise answer I saw, by @sschaef in a comment:

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

l.span(_>=0) match { case (left, Nil)      => left
                     case (left, x::right) => left ++ (x +: right.filter(_>=0)) }

Answer 2

You can do it in one pass provided you don't mind keeping a bit of state around - mind the var neg:

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

Answer 3

There are a lot of tail-recursive solutions, but they're all longer than they need to be.

def oneNeg(xs: List[Int]): List[Int] = {
  def loop(in: List[Int], out: List[Int], neg: Int): List[Int] = in match {
    case Nil => out
    case x :: rest =>
      if (neg < 0 && x < 0) loop(rest, out, neg)
      else loop(rest, x :: out, x min neg)
  }
  loop(xs, Nil, 0).reverse
}

If this is not a public-facing API, you can make it shorter yet by just exposing the inner method alone:

def oneNeg(in: List[Int], out: List[Int] = Nil, neg: Int = 0): List[Int] = 
  in match {
    case Nil => out.reverse
    case x :: rest =>
      if (neg < 0 && x < 0) oneNeg(rest, out, neg)
      else oneNeg(rest, x :: out, x min neg)
  }

Answer 4

A direct translation of the requirement is pretty clear, takes one pass over the list, and is functional:

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)

(The List around firstneg.head is just for the symmetry of ::: both sides)

Answer 5

It wouldn't be a proper functional programming question without a slightly-too-clever recursion+pattern matching answer.

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 6

You can try:

val list = List(1, 2, -4, 5, -6, -1, 3)
val index = list.indexWhere(_ < 0) + 1
list.take(index) ++ list.drop(index).filter(_ > 0)

Answer 7

This is an obvious work for fold operation!

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

var result = l.foldLeft((true, Vector.empty[Int])) {
  case ((f, r), x) if x >= 0 => (f, r :+ x)
  case ((f, r), x) if f => (false, r :+ x)
  case ((f, r), x) => (f, r)
}._2

println(result)  // Vector(1, 2, -4, 5, 3)

I used a vector as an intermediate structure; you can convert it to a list with toList, if you need it. Or you can use it instead of the Vector, but you will have to reverse the addition order (r :+ x => x :: r) and then reverse the list in the end with reverse method.

Answer 8

val l = List(1, 2, -4, 5, -6, -1, 3) 
val (left, right) = l.span(_ > 0)
val result = right.headOption match {
    case Some(n) => (left :+ n) ++ right.tail.filter(_ > 0)
    case None => left
}

Answer 9

Here is a tail-recursive way. Compared to m-z's answer, it iterates your list only one time, compared to Dimas answer, it does not use mutable state, so it is pure functional.

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)

Edit:

The above implementation provides a reversed result. In order to preserve order you can do following:

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 10

Here is tail recursive solution preserving order:

  def posNeg(xs: List[Int]): List[Int] = {
    @tailrec
    def go(tail: List[Int], res: List[Int]): List[Int] = {
      tail match {
        case h :: t =>
          if (h >= 0) go(t, h :: res)
          else (h :: res).reverse ::: t.filter(_ > 0)
        case _ => res
      }
    }
    go(xs, Nil)
  }

Answer 11

If you want to maintain the order (i.e., the position of the negative), you could do something like this:

val list = List(1, 2, -4, 5, -6, -1, 3)
val negIndex = list.indexWhere(_ < 0)
val positive = list.zipWithIndex.filter { case (num, index) =>
    num >= 0 || index == negIndex
}.map(_._1)

The negative requirement makes it hard to keep it more succinct than that. My strategy is to just grab the index of the first negative with indexWhere (will be -1 if there is none), then filter all the negatives out of the list, except for the index of the first negative. If the index was -1, no harm, no foul.