Scala: Converting From Number List To Cumulative List

Scala: 数列から累積値のリストを作る

 

目的

a[0], a[1], a[2], ... , a[n] のような数値が入ったリストを元に、

b[0] = a[0]
b[1] = a[0] + a[1]
b[2] = a[0] + a[1] + a[2]
...
b[n] = a[0] + a[1] + a[2] + ... + a[n] 

が成り立つ累積値のリスト b[0], b[1], b[2], ... , b[n] を作成したい。

 

コード

scanLeft (scan でも可) メソッドがまさに適役である。

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _)
res0: List[Int] = List(0, 1, 4, 9, 11, 15)

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _).tail
res1: List[Int] = List(1, 4, 9, 11, 15)

初期値 0 を元手に累積的に加算を行った後、tail で先頭の 0 を取り除いている。

 

数値を右から足し込みたい場合には、scanRight が使える。

scala> List(1, 3, 5, 2, 4).scanRight(0)(_ + _).init
res2: List[Int] = List(15, 14, 11, 6, 4)

体感としても、計算量 Θ(n) になっている模様。