7

We have a list of integers like: [1,4,5,6,6,7,9].

The idea is to generate a list with the same length and sums up till the current element like: [1,5,10,16,22,29,38].

In the Java world it would look like:

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
}

I know there exist more elegant and efficient solutions. My question is how to do something like this in Scala in more fuctional way?

Thx!

zmeda
  • 2,909
  • 9
  • 36
  • 56
  • 1
    This is a duplicate of at least http://stackoverflow.com/questions/4469538/scala-producing-the-intermediate-results-of-a-fold/4469590#4469590. – ziggystar Mar 24 '15 at 08:22

2 Answers2

8

You are looking for the scan combinator.

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

Remove the leading element with tail if you want I am not aware of a version of scan that does not take an initial value. The complexity is O(n) for this guy and you could implement it yourself with folding the list via an accumulator and a list (that contains past accumulators). The latter you take as a result.

uberwach
  • 1,119
  • 7
  • 14
4

@uberwatch's answer is the right one, but for the sake of completeness, here's the more "generic" functional solution using foldLeft:

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
dhg
  • 52,383
  • 8
  • 123
  • 144
  • Sorry pre-coffee but isn't vector a resizing array? This would lead (depending on the implementation) to like log n copy operations. My gut feeling tells me that taking a list and prepending(!) with a reverse afterwards should be faster. – uberwach Mar 24 '15 at 07:46
  • Welllllllll, `Vector`'s implementation actually doesn't work like that. It doesn't copy the elements every time, and the amortized cost is ["effectively constant"](http://docs.scala-lang.org/overviews/collections/performance-characteristics.html). So, for most cases, it's not going to make a difference. Of course, if you have huge lists in tight loops, then, yeah, *maybe*. But if that was really the performance bottleneck, I'd actually just implement your java approach: `Array`s and `while` loops is going to be the fastest way every time. – dhg Mar 24 '15 at 07:50