Scala: overflow despite use of Long when adding

Question

On 2.7.5.final, I'm attempting to add a Iterable list of Ints like so

def sum(xs: Iterable[Int]): Long = {
  var sum = 0L
  xs.foreach((x) => sum = sum + x)
  sum
}

println(sum(List(1, Integer.MAX_VALUE - 1)))
println(sum(Integer.MAX_VALUE - 1 to Integer.MAX_VALUE))
println(0L + Integer.MAX_VALUE - 1 + Integer.MAX_VALUE)

When I run, I get

2147483647
0
4294967293

And, you might say "use reduceLeft(_ + _)", but it seems to only be able to return the same type as elements in the list... but I want to accumulate to a Long, so I don't have overflow issues.

Update 2009-10-28

This is a bug in Range, as pointed out by Eastsun. It's been reported to the Scala team in ticket 2535

Answer 1

It's a bug of Range. There is the source code of Range's foreach method:

override def foreach(f: Int => Unit) {
if (step > 0) {
  var i = this.start
  *val until = if (inInterval(end)) end + 1 else end*      //bug here!!!

  while (i < until) {
    f(i)
    i += step
  }
} else {
  var i = this.start
  val until = if (inInterval(end)) end - 1 else end

  while (i > until) {
    f(i)
    i += step
  }
}

}

Answer 2

Eastsun's answer gave a very good reason why you calculation overflows. As a workaround I would redefine the sum function to use foldLeft, which allows you to specify the accumulator.

def sum(xs: Iterable[Int]): Long =
  xs.foldLeft(0L)(_ + _)

or using the shorthand for foldLeft (which I quite like as it puts the starting value of the fold in front of the Iterable you are trying to fold).

def sum(xs: Iterable[Int]): Long =
  (0L /: xs)(_ + _)

In both cases, the code you were trying to run gives the correct results.

-- Flaviu Cipcigan