foldLeftのメモ - voidy21の日記

Design Recipe 別館 Blog - Scala と Ruby で単語の出現頻度を調べて多い順にソートするのプログラム見て勉強になったので自分の中で整理

List中の出現数を求めているプログラムがあって、

val gosanke = List("Goro", "Hideki", "Hiromi", "Hideki", "Goro", "Hideki")
val countByGosanke = (Map.empty[String, Int] /: gosanke) { (r, e) =>
  r + (e -> (r.getOrElse(e, 0) + 1))
} 
//countByGosankeはMap((Goro,2), (Hideki,3), (Hiromi,1))になる

となってたんだけど、これが自分の中であんまりピンとこなくて色々調べた。

/: はfoldLeft

記事中でも触れられているのであんまり説明の必要が無いが書いておく

配列の合計値(Java)

例えば、Javaで配列の合計値を求めたいときは

int sum = 0;
for(int i in new int[] {1,2,3,4,5}) sum += i;

みたいに書くと思う

配列の合計値(Scala)

scalaのfoldLeftを使うと、

def add(a:Int, b:Int) = a + b
val sum = (1 to 5).foldLeft(0)(add)

みたいに書ける。foldLeftの引数の0は初期値を与えている！
aとbがここでは何かというと、

a ・・・ループして足される合計値。初期値はfoldLeftの引数である0。なので0,1,3,6,10,15と変化。
b ・・・リスト(1 to 5)のループごとのそれぞれの値(1,2,3,4,5と変化)

無名関数つかう

ただ、scalaにも当然無名関数があって、=>で書けるので、

val sum = (1 to 5).foldLeft(0)((a:Int,b:Int) => a + b)

と書ける。

型推論する

ここで、aとbは(1 to 5)から自動的に型推論できてIntが不要なので、

val sum = (1 to 5).foldLeft(0)((a,b) => a + b)

となる。

さらに型推論する

さらにscalaではこれの省略が可能で、

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

と書ける。

/:ってなんぞ

次は/:について書く。結果から書くと、上のコードは次と等価になっている。

val sum = (0 /: (1 to 5)) (_ + _)

でもこれは少し飛び過ぎなので、ちょっと補足すると、scalaは

引数が1個のメソッドを呼び出すときは、ピリオドと括弧を省略することができる(rubyと同じ)
演算子はメソッド

でもInt型に/:メソッドがあるのかというとそうではなくて、

メソッド名の末尾にコロンが付くと右被演算子になる

ので、(1 to 5)のList型が持ってるメソッドになる。
で、この/:メソッドというのがfoldLeftと同じなので先程の

val sum = (0 /: (1 to 5)) (_ + _)

というように書ける。

ここまできてアレですが

List型はsumメソッド持ってるので

val sum = (1 to 5).sum

でいいので注意。

かなり脱線した！！

最近だんだんわかってきた

ここまでくると先程の

val gosanke = List("Goro", "Hideki", "Hiromi", "Hideki", "Goro", "Hideki")
val countByGosanke = (Map.empty[String, Int] /: gosanke) { (r, e) =>
  r + (e -> (r.getOrElse(e, 0) + 1))
} 
//countByGosankeはMap((Goro,2), (Hideki,3), (Hiromi,1))になる

の構造がわかってくる。
まず、

Map.empty[String, Int]

は初期値（空のMap）になっていて、

 (r, e) =>  r + (e -> (r.getOrElse(e, 0) + 1))

のrとeは

r・・・初期値に空のMap[String, Int]が代入されて、その後色々と変化する
e・・・リストgosankeの各要素（Goro,Hideki,Hiromi,Hideki,Goro,Hidekiの順番)

になっている。

ほむほむ

次に、

e -> (r.getOrElse(e, 0) + 1)

って何かを考える。

->ってなんぞ？

scalaの全てのオブジェクトから呼び出せるメソッド
キーと値を格納する2要素のタプルを返す

例えば1 -> 2 とすると (1).->(2)が呼ばれて(1,2)が返却される。
つまり

e -> (r.getOrElse(e, 0) + 1)
// e がキー
// (r.getOrElse(e, 0) + 1) が値
// のタプル

になる。

getOrElseってなんぞ？

MapクラスのgetOrElseメソッド*1は引数を2つとり、
キーとデフォルト値を指定する。
返却される型はデフォルト値の型と同じになる。
キーで指定された要素がMapの中に見つからない場合はデフォルト値を返却し、
キーが見つかった場合はその値を返却する。

なので

e -> (r.getOrElse(e, 0) + 1)

は、

キーがリスト(Goro,Hideki,Hiromi,Hideki,Goro,Hideki)の各要素 e
値が今までのループによって作成されたMap r のキー e の値に1を加えたもの（なければ値は1）

となる。

r + (e -> (r.getOrElse(e, 0) + 1))の + ってなんぞ？

+メソッド
Mapの+メソッドはタプルを引数にとる
- キーが既に存在する場合は置き換える
- キーが存在しない場合は追加する

こんな感じで解釈したが

そんな解釈で大丈夫か？

*1:Option型のgetOrElseメソッドの方が一般的なので注意