Functional Programming Principles in Scala (Week 6: Collections)

==== Lectures ====
Lecture 6.1 - Other Collections (20:45)
[Vector]
32個のユニットで深くなる木構造。
Listよりランダムアクセス、bulk operationに適している。
O(log(N))
[Seq]
List,Vector,Rangeの親クラス。さらにSetと共通の親はIterable
filter,map,flatMap,exists,forall,zip,unzip,sum,product,max,min等が使える。
x => x match { case p1 => e1 ... } は { case p1 => 1 e1 ... } とも書ける。

Lecture 6.2 - Combinatorial Search and For-Expressions (13:12)
[for]
Nestしているcollectionはmapやfilterを多重に使うよりもforとyieldを使った方が分かりやすい。
Chapter 23 of Programming in Scala, First Edition: For Expressions Revisited

Lecture 6.3 - Combinatorial Search Example (16:54)
[Set]
Iterableのsub type。map等Seqの操作の大部分が使える。
unordered, not duplicate, fundamental operation is contains
[N-Queen問題]
forの combinational searchの例としてSetも使って解いてみる。

Lecture 6.4 - Queries with For (7:50)
[for]
forの combinational search はSQLなどデータベースのQueryと同じ。
search元のデータをSetにすればsearch結果もSetになる。

Lecture 6.5 - Translation of For (11:23)
[for]
forとmap, flatMap, filterの透過性について。
scalaのcompilerはforをmap, flatMap, lazy filter(withFilter)に変換している。
forの方が見やすいから。
同じアイデアが使われている。ScalaQuery, Slick, Microsoft's LINQ。

Lecture 6.6 - Maps (22:39)
[Map]
連想配列、辞書。
withDefaultで値が場合にdefault値を返すように出来る。
Map(1 -> "a", 2 -> "b") ++ Map(2 -> "c", 3 -> "d") は Map(1 -> "a", 2 -> "c", 3 -> "d")
ListにgroupBy(element => key)でke -> List(e1, e2...)のMapが作れる。

[Option]
None,Some(x) 値がない場合も統一的に扱える。
Mapのget methodを使えばOption typeが取れる。

Lecture 6.7 - Putting the Pieces Together (20:35)
[example of collection]
今週の課題の内容と似ている。辞書から可能なwordsを選ぶ。
既刊の本の問題から取っている。既に色々な言語(java, c, c++, python等)でテスト済。
スクリプト言語だと100loc, 他の言語だと200-300locの規模。そこそこのサイズ。
scala.io.Sourceで辞書をダウンロードして使う。
同じことは2回書かない様にする。元ネタを変換する。
境界条件から考える。nullや1個の時。
scala collectionsの利点: easy, concise, safe, fast, universal

==== Assignments ====
[Anagrams]
英語の綴りを変更して意味のある文を見つける事。
?? プログラムで意味があるかをどうやって判断する??
=> 単語の辞書が用意されている。
計算量がものすごく多くなりそうだが大丈夫か?
計算量を減らす追加課題もあるがとりあえず時間が無いのでパス。

毎回パズル的な問題で頭の体操としては面白い。

今回も1回目の提出で満点!!

[IntelliJ]
worksheetとプログラムと結果のずれがなくなった。
バージョンアップのせいか、コメントなしにしたせいか?

==== Etc. ====
Lectureは1.5倍速で字幕なしで見ている。大体は理解できている気がする。
Programming in Scala, First Editionの予習が追いついていない所が出てきた。

==== Log ====
2014/06/02 00:45 Lecture
2014/06/02 00:20 Lecture
2014/06/03 00:45 Lecture
2014/06/04 00:45 Lecture
2014/06/05 00:20 Assignments
2014/06/06 02:00 Assignments
2014/06/07 01:15 Assignments