CODEWITHSUNDEEP
scalafunctional-programming
ziggystar
ziggystar

Reputation: 28680

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.

Upvotes: 17

Views: 8082

Answers (4)

Dario
Dario

Reputation: 49218

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)

Upvotes: 33

hbatista
hbatista

Reputation: 1237

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}}

Upvotes: 6

Rex Kerr
Rex Kerr

Reputation: 167891

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.

Upvotes: 7

IttayD
IttayD

Reputation: 29123

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

Upvotes: 9

Related Questions