scala コレクションライブラリ foldLeft / foldRight
scala コレクションライブラリ foldLeft / foldRight
foldLeft
foldLeft はリストの要素を左から順にfを使って「畳み込む」。
リストの要素に対して左側から関数をする、関数の結果と次の要素を取り出し関数を適用する、という風に再帰的に処理が繰り返される。
fold = 畳み込む という意味である。
codeで表すと以下のようになる
def foldLeft[B](z: B)(f: (B, A) ⇒ B): B
foldLeftはリストの左側からfを適用していく。zは初期値だ。
リストに加算を行う式は以下だ
scala> List(1, 2, 3).foldLeft(0)((x, y) => x + y) res0: Int = 6
foldLeft が行う処理
List(1, 2, 3).foldLeft(0)((x, y) => x + y)
上記の式が計算する順序は以下だ。初期値を0としてListの先頭から加算を繰り返す。そしてリストの要素を一つの要素にたたみ込んで行く。
+
/ \
+ 3
/ \
+ 2
/ \
0 1
演習問題
foldLeftを用いて、Listの要素を反転させる次のシグニチャを持ったメソッドreverseを実装してみましょう：
def reverse[T](list: List[T]): List[T] = ???
コンスを使えばイケそう
scala> def reverse[T](list: List[T]): List[T] = { | val rev: List[T] = Nil; | list.foldLeft(rev)((r, x) => x :: r); | } reverse: [T](list: List[T])List[T] scala> List(1,2,3,4,5).reverse res4: List[Int] = List(5, 4, 3, 2, 1)
なるほど。 1 :: Nil みたいにコレクション型を後置しないといけないんだね
foldRight
これはそのまま、右からの畳み込み。
codeで表現すると次になる。
def foldRight[B](z: B)(op: (A, B) ⇒ B): B
初期値とリストの右から要素を取り出し、関数を適用。その結果と1つ左の要素を取り出し関数を適用、という風に順番にたたみ込んで行く。
+
/ \
1 +
/ \
2 +
/ \
3 0
foldLeftが理解できているとわかりやすいね
練習問題1
Listの全ての要素を足し合わせるメソッドsumをfoldRightを用いて実装してみましょう。sumの宣言は次のようになります。なお、Listが空のときは0を返してみましょう。
def sum(list: List[Int]): Int = ???
自分の答え
これは簡単だね
scala> def sum(list: List[Int]): Int = { | if (list.isEmpty) { return 0; } | list.foldRight[Int](0)((x, y) => x+y); | } sum: (list: List[Int])Int scala> List(1,2,3,4,5).sum res3: Int = 15
模範解答
def sum(list: List[Int]): Int = list.foldRight(0){(x, y) => x + y}
え、まじか。戻り値デフォルトで0なのね。これはfoldRightの仕様っぽいね
次の問題。
練習問題2
Listの全ての要素を掛け合わせるメソッドmulをfoldRightを用いて実装してみましょう。mulの宣言は次のようになります。なお、Listが空のときは1を返してみましょう。
def mul(list: List[Int]): Int = ???
自分の答え
これは模範解答通りだった。嬉しい。
scala> def mul(list: List[Int]): Int = list.foldRight(1)((x,y) => x*y); mul: (list: List[Int])Int scala> mul(List(1,2,3,4,5)) res4: Int = 120
練習問題3
mkStringを実装してみましょう。mkStringそのものを使ってはいけませんが、foldLeftやfoldRightなどのListに定義されている他のメソッドは自由に使って構いません。ListのAPIリファレンス を読めば必要なメソッドが載っています。実装するmkStringの宣言は
def mkString[T](list: List[T])(sep: String): String = ???
となります。残りの2つのバージョンのmkStringは実装しなくても構いません。
さて、急にレベル上がったな。
mkString はList内の要素を結合する関数だったはず。
自分の答え
あんまり綺麗な答えではないな。
scala> def mkString[T](list: List[T])(sep: String): String = { | list.foldLeft("")((x, y) => { | if (x.isEmpty) {x + y.toString} | else {x + sep + y.toString} | }); | } mkString: [T](list: List[T])(sep: String)String scala> mkString[Int](List(1,2,3))(",") res13: String = 1,2,3
模範解答
確かに綺麗だけどまだmatch教えてくれてないやん!!!! ありかよ!!w
def mkString[T](list: List[T])(sep: String): String = list match { case Nil => "" case x::xs => xs.foldLeft(x.toString){(x, y) => x + sep + y} }
2個目のcaseが気になった。
x::xs => xs.foldLeft(x.toString){(x, y) => x + sep + y}
x::xs は なんらかのlistが2つ連結したもの と見立てることができる。
そう考えると x = Nil, xs = 処理したいList と考えてもいい。
scala> Nil :: List(1,2,3) res14: List[Any] = List(List(), 1, 2, 3)
こう見ると xs には処理対象としたい list が入ってくるのがわかりやすい。
ということで今回はここまで。
