Scala: Producing the intermediate results of a fold

Question

I've come across the problem of maintaining a state throughout a map operation several times. Imagine the following task:

Given a List[Int], map each element to the sum of all preceding elements and itself.
So 1,2,3 becomes 1, 1+2, 1+2+3.

One solution I've come up with is:

scala> val a = 1 to 5                                                
a: scala.collection.immutable.Range.Inclusive with scala.collection.immutable.Range.ByOne = Range(1, 2, 3, 4, 5)

scala> a.foldLeft(List(0)){ case (l,i) => (l.head + i) :: l }.reverse
res3: List[Int] = List(0, 1, 3, 6, 10, 15)

But somehow I feel that there has to be a simpler solution.

Answer 1

You're trying to compute the sequence of partial sums.

The general operation for computing such accumulations is not fold but scan, though scan is expressible through fold in the way you showed (and fold is actually the last element of the list produced by scan).

As to Scala, I'll give this example

scala> scanLeft(List(1,2,3))(0)(_ + _)
res1: List[Int] = List(0, 1, 3, 6)

Answer 2

@Dario gave the answer, but just to add that the scala library provides scanLeft:

scala> List(1,2,3).scanLeft(0)(_ + _)
res26: List[Int] = List(0, 1, 3, 6)

Answer 3

The scan answers are the best ones, but it's worth noting that one can make the fold look nicer and/or be shorter than in your question. First, you don't need to use pattern matching:

a.foldLeft(List(0)){ (l,i) => (l.head + i) :: l }.reverse

Second, note that foldLeft has an abbreviation:

(List(0) /: a){ (l,i) => (l.head + i) :: l }.reverse

Third, note that you can, if you want, use a collection that can append efficiently so that you don't need to reverse:

(Vector(0) /: a){ (v,i) => v :+ (v.last + i) }

So while this isn't nearly as compact as scanLeft:

a.scanLeft(0)(_ + _)

it's still not too bad.