In Scala, how do I fold a List and return the intermediate results?

Question

I've got a List of days in the month:

val days = List(31, 28, 31, ...)

I need to return a List with the cumulative sum of days:

val cumDays = List(31, 59, 90)

I've thought of using the fold operator:

(0 /: days)(_ + _)

but this will only return the final result (365), whereas I need the list of intermediate results.

Anyway I can do that elegantly?

Answer 1

Scala 2.8 has the methods scanLeft and scanRight which do exactly that.

For 2.7 you can define your own scanLeft like this:

def scanLeft[a,b](xs:Iterable[a])(s:b)(f : (b,a) => b) =
  xs.foldLeft(List(s))( (acc,x) => f(acc(0), x) :: acc).reverse

And then use it like this:

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

Answer 2

Fold into a list instead of an integer. Use pair (partial list with the accumulated values, accumulator with the last sum) as state in the fold.

Answer 3

Works on 2.7.7:

def stepSum (sums: List [Int], steps: List [Int]) : List [Int] = steps match { 
     case Nil => sums.reverse.tail                                                  
     case x :: xs => stepSum (sums.head + x :: sums, steps.tail) }

days
res10: List[Int] = List(31, 28, 31, 30, 31)

stepSum (List (0), days) 
res11: List[Int] = List(31, 59, 90, 120, 151)

Answer 4

Fold your list into a new list. On each iteration, append a value which is the sum of the head + the next input. Then reverse the entire thing.

scala> val daysInMonths = List(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
daysInMonths: List[Int] = List(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

scala> daysInMonths.foldLeft(Nil: List[Int]) { (acc,next) => 
     | acc.firstOption.map(_+next).getOrElse(next) :: acc    
     | }.reverse                                             
res1: List[Int] = List(31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)

Answer 5

val daysInMonths = List(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

//Using foldRight. Much efficient.
val rDaysInMonths = daysInMonths.tail.reverse
val cumulatedRight = rDaysInMonths.foldRight(daysInMonths.head :: Nil)((next, acc) => {
  (acc.head + next) :: acc
}).reverse

//Using foldLeft
val cumulatedLeft = daysInMonths.tail.foldLeft(daysInMonths.head :: Nil)((acc, next) => {
  acc ::: (acc.last + next) :: Nil 
})

Answer 6

I'm not sure why everybody seems to insist on using some kind of folding, while you basically want to map the values to the cumulated values...

val daysInMonths = List(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

val cumulated = daysInMonths.map{var s = 0; d => {s += d; s}}

//--> List[Int] = List(31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)