Scala Partialsumme mit aktuellen und allen früheren Elementen in der Liste

Question

Wir haben eine Liste von ganzen Zahlen wie: [1,4,5,6,6,7,9].

Die Idee ist, eine Liste mit der gleichen Länge zu generieren und bis zum aktuellen Element wie folgt zusammenzufassen: [1,5,10,16,22,29,38].

In der Java-Welt würde es wie folgt aussehen:

int sum = 0; 
int[] table = {1,4,5,6,6,7,9} 
int[] res = new int[table.length] 
for(int i=0; i<table.length; i++) { 
    sum += table[i] 
    res[i] = sum 
} 

ich weiß, gibt es mehr elegante und effiziente Lösungen. Meine Frage ist, wie man so etwas in Scala besser machen kann?

Thx!

Answer 1

Sie suchen nach dem Scan-Kombinator.

List(1,4,5,6,6,7,9).scanLeft(0)(_ + _) 
res1: List[Int] = List(0, 1, 5, 10, 16, 22, 29, 38) 

Leitelements mit Schwanz entfernen, wenn ich bin mir nicht bewusst eine Version von Scan möchten, die nicht einen Anfangswert nimmt. Die Komplexität ist O (n) für diesen Typ und Sie könnten es selbst implementieren, indem Sie die Liste über einen Akkumulator und eine Liste (die frühere Akkumulatoren enthält) zusammenfalten. Letzteres nehmen Sie als Ergebnis.

Answer 2

@ uberwatch Antwort ist die richtige, aber aus Gründen der Vollständigkeit, hier ist die weitere „generische“ funktionale Lösung foldLeft mit:

val xs = Vector(1,4,5,6,6,7,9) 
val (sumList, sum) = 
    xs.foldLeft((Vector.empty[Int], 0)) { 
    case ((list, total), x) => 
     val newTotal = x + total 
     (list :+ newTotal, newTotal) 
    } 
// sumList: Vector(1, 5, 10, 16, 22, 29, 38) 
// sum: Int = 38