Как вернуть все положительные значения и первое отрицательное число в списке, используя функциональное программирование?

Ответ 1

Вот хвост-рекурсивный путь. По сравнению с ответом m-z он повторяет ваш список только один раз, по сравнению с ответом Димаса, он не использует изменчивое состояние, поэтому он является чисто функциональным.

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

Вышеупомянутая реализация обеспечивает обратный результат. Чтобы сохранить порядок, вы можете сделать следующее:

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)

Ответ 2

Это не был бы правильный вопрос о функциональном программировании без ответа с слишком умной рекурсией + шаблоном.

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

Ответ 3

Вы можете сделать это за один проход, если вы не возражаете поддерживать немного состояния - подумайте var neg:

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

Ответ 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 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 справедливо только для симметрии ::: с обеих сторон)

Ответ 5

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
}

Ответ 6

Это очевидная работа для операции сгиба!

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)

Я использовал вектор как промежуточную структуру; вы можете преобразовать его в список с toList, если вам это нужно. Или вы можете использовать его вместо Vector, но вам придется отменить порядок добавления (r :+ x = > x :: r), а затем перевернуть список в конце с помощью метода reverse.

Ответ 7

Если вы хотите сохранить порядок (т.е. положение отрицательного), вы можете сделать что-то вроде этого:

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)

Отрицательное требование затрудняет его сжатие. Моя стратегия состоит в том, чтобы просто захватить индекс первого отрицательного значения с помощью indexWhere (будет -1, если его нет), а затем filter все отрицательные элементы из списка, за исключением индекса первого отрицательного. Если индекс был равен -1, никакого вреда не было.

Ответ 8

Ниже приведен порядок сохранения хвостового рекурсивного решения:

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

Ответ 9

Существует много рекурсивных решений, но они все дольше, чем они должны быть.

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
}

Если это не общедоступный API, вы можете сделать его короче, просто разоблачив только внутренний метод:

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

Ответ 10

Вот улучшение на наиболее краткий ответ, который я увидел, @sschaef в комментарий:

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

Ответ 11

Вы можете попробовать:

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