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.

score 33 · Accepted Answer · edited Dec 30 '22 at 11:49

33

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)

edited Dec 30 '22 at 11:49

ziggystar

28,410
9
72
124

answered Dec 17 '10 at 10:29

Dario

48,658
8
97
130

Indeed, there is a scanLeft function, which does exactly what I need. If you or someone else will add a valid scala example of its usage, I'll accept this answer. – ziggystar Dec 17 '10 at 10:34
Edited the answer with some example I found. Using nicer syntax, `a scanLeft(0) { (a, b) => a + b }` might stil work though – Dario Dec 17 '10 at 10:45
4

scala> List(1,2,3).scanLeft(0)(\_+\_) – ziggystar Dec 17 '10 at 14:37
Funny enough, following your link, it says "the following example is from SO". – ziggystar Dec 17 '10 at 15:47

score 9 · Answer 2 · answered Dec 17 '10 at 13:12

9

@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)

answered Dec 17 '10 at 13:12

IttayD

28,271
28
124
178

score 7 · Answer 3 · answered Dec 17 '10 at 15:53

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.

This is useful when your binary op's type is not (B, B) => B, but (C, B) => C — poroszd, Jul 07 '14 at 20:24

score 6 · Answer 4 · answered Dec 17 '10 at 18:33

6

I like to fold around just like everybody else, but a less FP answer is very concise and readable:

 a.map{var v=0; x=>{v+=x; v}}

answered Dec 17 '10 at 18:33

hbatista

1,207
9
12

Nitpicking, but I wonder if the order is guaranteed when `map` calls its parameter function. – HRJ Jun 07 '11 at 12:07
@HRJ - It is guaranteed for serial collections. It is not guaranteed for parallel collections, but then you have worse problems (not synchronized on `v`). – Rex Kerr Jun 07 '11 at 13:00

Scala: Producing the intermediate results of a fold

4 Answers4

Linked