Incrementing Variable in a foldLeft

Question

I have Scala code like this

var i = 1
for(e <- array) {
    acc += e * i
    i += 1
}

I need to multiply the first element in the array by 1, the next by 2, the next by 3 and so on adding it all into an accumulator. I feel that there is a better way of doing this in Scala, maybe even with folding?

Ostium

Answer 1

val x = List(1,1,1,1,1,1)
(((0,1) /: x){case ((acc, mult), l) => (acc + (l * mult), mult + 1) })._1

In other words, starting with an accumulator of 0 and a multiplier of 1, fold each element of the list in, changing the accumulator to acc + (l * mult) and incrementing the multiplier by 1. We get the final multiplier out at the end as well, so we call ._1 to just get the accumulator.

Edit: As @RexKerr points in his answer below (and the comment), if performance is a major concern then you're better off using an explicit recursive method.

Manolo

Answer 2

"Better" depends on what your goals are. Short and clear? Probably

{ for (i <- array.indices; e = array(i)) yield (i+1)*e }.sum

or

array.indices.map(i => (i+1)*array(i)).sum

(or slightly faster, since you create the intermediates as you go:

array.indices.iterator.map(i => (i+1)*array(i)).sum

).

You should usually be short and clear.

Fast? Then you'll need to go old-school:

var i = 0
var acc = 0
while (i < array.length) {
  acc += (i+1)*array(i)
  i += 1
}

or use recursion

def sum(a: Array[Int], i: Int = 0, acc: Int = 0): Int =
  if (i >= a.length) acc else sum(a, i+1, (i+1)*a(i) + acc)
sum(array)

Stoneman

Is explicit recursion likely to be any faster than a fold? Only advantage I can see is not allocating the tuple... – Manolo

@Manolo - If you're doing lightweight operations like addition of integers, not allocating the tuple is huge (10x speedup). Also, collections are not specialized for primitives which means every integer has to be boxed, while recursion can use primitive types. Also huge (both together gives ~20x-30x speedup). – Stoneman

Hey @Rex, do you mind explaining why you are mapping over the iterator in the 3rd example? Mapping over the indices seems to do the trick. – Labuan

@Labuan - The 2nd example creates a whole new collection (a Vector, actually) to store the intermediate results. Using an iterator prevents this--it does the mapping on the fly--so despite the extra overhead from advancing from item to item, it's faster overall. But it's not as short and clear, so only do it if the overhead of the extra collection is a problem. (I think it is clearer than a fold, though.) – Stoneman

Cool, I'll start using that more often now... Cheers! – Labuan

The third suggestion is directly equivalent to the first. The second one shows it's all too easy to unintentionally need wasteful intermediate state. – Inapposite

@Inapposite - The first and second suggestions are equivalent. Plus you're already wastefully boxing integers, so who's counting? – Stoneman

Sorry to nit-pick over trivia, but the first has an implied call to get the iterator, so it's equivalent to the third. – Inapposite

@Inapposite - Good grief, why do you think that? Go check -Xprint:typer or some bytecode! Also, did you realize that it packs the e in a tuple? – Stoneman

Answer 3

I prefer zipWithIndex which is simpler to read:

array.zipWithIndex.map { case (e, i) => e * (i + 1) }.sum

Modla

but then you iterate over the array twice from my understanding of that method, correct? – Ostium

Three times. zipWithIndex and map both iterate over the array and sum is implemented via foldLeft. So my approach is certainly not the fastest – Modla

If you use .view on array first, it will only be one pass, but you have to deal with the overhead of .view. Pick your poison. – Skippet

@Skippet could you expand on this answer a bit? Why does using .view remove the need for the compiler to iterate over the array three times for .zipWithIndex, .map and .sum? – Ostium

@Ostium .view makes the functions get lazily evaluated, so I don't think zipWithIndex and the map don't evaluated until sum time. At that time, each item in the new array that's getting summed over is computed one by one, so the array is only iterated over once. – Skippet

Answer 4

I am not sure if what I suggest is a better way to do it or not, as it is more functional (== it will perform slower):

(0 /: (array zipWithIndex)) {(a, i) => (i._1 * (i._2 + 1)) + a}

This does perform foldLeft on an array which is produced by zipWithIndex method in http://www.scala-lang.org/api/current/index.html#scala.Array

zipWithIndex simply zips the elements of a collection with their indices.

Boggers