scala - foldLeft заполняет смежные нули с порядковыми номерами

Question

У меня есть конкретный случай в foldLeft

scala> val nums = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)
nums: List[Int] = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)

Мне нужно получить вывод, заполнив непрерывные нули порядковыми номерами, т.е. 2,3,4

требуемый вывод:

List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1) 

И мне действительно нужно применить это к списку [(String, Int)]

от

List(("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1))

до требуемого выхода

List(("a",1),("b",1),("b",2),("a",1),("a",2),("a",3),("d",1),("d",2),("d",3),("c",1),("c",2), ("c",3), ("c",4), ("c",5), ("d",1), ("a",1))

Я пытаюсь использовать List [Int], как показано ниже, но получаю сообщение об ошибке

scala> nums.foldLeft(List[Int]())( (m:List[Int],n:Int) => { val p = if(n==0) m.last+1 else n; m.++ List(p) })
<console>:26: error: missing argument list for method ++ in class List
Unapplied methods are only converted to functions when a function type is expected.
You can make this conversion explicit by writing `$plus$plus _` or `$plus$plus(_)(_)` instead of `$plus$plus`.
       nums.foldLeft(List[Int]())( (m:List[Int],n:Int) => { val p = if(n==0) m.last+1 else n; m.++ List(p) })
                                                                                                ^

scala>

Как это исправить, а также применить логику к List [(String, Int])?.

Answer 1

Обратите внимание, что версия slow равна O(n^2) из-за вложенных вызовов на .last (что составляет O(n) в списке).

def slow(list: List[(String, Int)]): List[(String, Int)] =
  list.foldLeft(List[(String, Int)]()) {
    (m: List[(String, Int)], n: (String, Int)) => {
      val p = if (n._2 == 0) (n._1, m.last._2 + 1) else n
      m :+ p
    }
  }

Вы можете получить O(n)решение путем построения списка путем добавления к голове и обращения его к концу:

def fast(list: List[(String, Int)]): List[(String, Int)] =
  list.foldLeft(List[(String, Int)]()) {
    (m: List[(String, Int)], n: (String, Int)) => {
      val p = if (n._2 == 0) (n._1, m.head._2 + 1) else n
      p +: m
    }
  }.reverse

На моем компьютере для списка размером 32000 быстрый вариант занимает 18 мс, а медленный -6 секунд.

Answer 2

На самом деле, метод scanLeft больше подходит, чем foldLeft для этого вопроса. Вот оно:

Для List[Int]:

scala> val nums = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)
nums: List[Int] = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)

scala> nums.scanLeft(0){ (r, n) => if(n == 0) r + 1 else n }.tail
res1: List[Int] = List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1)

Для List[(String Int)]:

scala> val xs = List(("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1))
xs: List[(String, Int)] = List((a,1), (b,1), (b,0), (a,1), (a,0), (a,0), (d,1), (d,0), (d,0), (c,1), (c,0), (c,0), (c,0), (c,0), (d,1), (a,1))

scala> xs.scanLeft(("", 0)){ case((_, r), (c, n)) => (c, if(n == 0) r+1 else n) }.tail
res2: List[(String, Int)] = List((a,1), (b,1), (b,2), (a,1), (a,2), (a,3), (d,1), (d,2), (d,3), (c,1), (c,2), (c,3), (c,4), (c,5), (d,1), (a,1))

Это решение даже работает, если первое число равно нулю, решение @Markus Appel в этом случае не работает.

Answer 3

m.++ List(p) недопустимый синтаксис Scala. Это должно быть m ++ List(p).

Но вы также можете просто использовать оператор :+.

Пример (включая только Int и (String, Int)):

val stringsAndNums = List(
  ("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1)
)

// Without strings

val nums = stringsAndNums.map{case (a: String, b: Int) => b} 

println(
  nums.foldLeft(
    List[Int]()
  )(
    (m: List[Int], n: Int) => {

      val p = if(n == 0) m.last + 1 else n

      m :+ p
    }
  )
)

// With strings

println(
  stringsAndNums.foldLeft(
    List[(String, Int)]()
  )(
    (m: List[(String, Int)], n: (String, Int)) => {

      val p = if(n._2 == 0) (n._1, m.last._2 + 1) else n

      m :+ p
    }
  )
)

Результат:

List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1)
List((a,1), (b,1), (b,2), (a,1), (a,2), (a,3), (d,1), (d,2), (d,3), (c,1), (c,2), (c,3), (c,4), (c,5), (d,1), (a,1))

Попробуйте!