Search code examples
scalafunctional-programming

Scala: Producing the intermediate results of a fold

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.

Solution

  • 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).

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