[Scala] 累積和の求め方(foldLeftとscanLeft)

AtcoderにScalaを使って参加しています。

問題を解いていると累積和を使うことで計算量が小さくなる問題に出くわします。例えば、[1, 2, 3, 4, 5] の累積和を求めると、[1, 3, 6, 10, 15]となります。当該インデックスまでの値を合算した値の配列です。

で、毎回for式でぐるぐるまわして足していたんだけど、いかにも手続き的な処理になっていて、もう少しうまくかけないものかなと思っていました。

単純に配列内の値の合算値ならば、foldLeftを使用して以下のように書けます。出力値は15になります。

val sum = (1 to 5).foldLeft(0)(_+_)
println(sum)

もっと単純に、sumメソッドを使ってしまうとよりわかりやすくなります。

val sum = (1 to 5).sum
println(sum)

こんな感じで、累積和を求める方法がないかなとcollectionのメソッドを探していて、scanLeftを見つけました。
「Produces a iterable collection containing cumulative results of applying the operator going left to right, including the initial value.」ということで、初期値に対して、指定した関数を適用してその結果をcollectionにしてくれるものののようです。なんでscanなんだろう。foldがたたんでいって一つの値になるのに対して、全項目を走査して結果もcollectionになるからなのか。。

以下の結果は、"Vector(0, 1, 3, 6, 10, 15)"になります。

val sum = (1 to 5).scanLeft(0)(_+_)
println(sum)

次に累積和を使う問題に出くわしたら使ってみようと思います。collection系の便利メソッドはもっと積極的に使っていかなければ。