Functional Programming Principles in Scala (Week 7: Lazy Evaluation)

==== Lectures ====
Lecture 7.1 - Structural Induction on Trees (15:10)
[IntSets]
BinaryTree構造のIntSetsの実装の正しさの証明をInduction(Reasoning)で行う。
制約条件を上げて一つずつ置き換えで証明する。
Online講義ではoptional。大学ではテストに出る?

Lecture 7.2 - Streams (12:12)
[Stream]
Stream: tailが必要な時のみに評価されるList。
不要な部分をあらかじめ計算してしまうのを抑制できる。
無限集合も扱える。
遅延評価。tailを関数値として未評価で保持している?
consのtailにby-name parameterを使う。Listでは普通のparameter。
Listのmethodはほとんど使える。
x :: xs はListになる。
x #:: xs だとStreamになる。
Streamは過去にアクセスした要素を覚えているので、メモリを消費する。
Iteratorは使い捨てなのでメモリは消費しないが、複数回要素にアクセスできない。

Lecture 7.3 - Lazy Evaluation (11:38)
[lazy]
遅延評価。必要な時に計算。
一度計算したら結果を保持して再利用。何回計算しても同じなのが重要。
by-nameでは毎回計算する??
副作用があると計算順序やタイミングが読みにくいので使いにくい。
lazy val x = exprは一回しか計算されない。def x = expr は毎回計算。
Stream.consのby-name parameterもlazy valにすれば効率が良くなる。

Lecture 7.4 - Computing with Infinite Sequences (9:01)
[Infinite Streams]
def from(n: Int): Stream[Int] = n #:: from(n+1)
from(n+1)がlazyで必要になるまで実行されない。
終了条件が必要ない。
Eratosthenesの篩もそのまま実施出来る。
√2のような無限小数も求める事が出来る。

Lecture 7.5 - Case Study: the Water Pouring Problem (31:45)
[Water Pouring Problem]
既にpyhtonで解かれた例がある。
pure functionalで一般的な解法。
Streamを使う。
recursiveを同等のfoldで表現出来る場合が多い。慣れないと難しいかも。
Name evrything you can.
natural scopes.
refactoring.

Lecture 7.6 - Course Conclusion (5:34)
[Conclusion]
効果関数。パターンマッチング、不変集合、参照透過、strict/lazy/by-name評価
更なるtopic: mixed with mutable, parallelism, DSL

==== Assignments ====
[Bloxorz]
flashのゲームみたい。そのソルバーを開発する。古典的な人工知能っぽい問題。
最終課題という事でそこそこの規模もあり、複数のファイルで構成されてる。
Water Pouring Problemと同様に幅優先探索で解を求める。
1回目の提出では解が存在しない場合に無限ループに入っていて減点。19.3/20
2回目の提出で満点!!

gradingは通ったが、fromの実装が講師の意図通りなのかちょっと不安。
Water Pouring Problemとほぼ同様にしてみたが。。。

[IntelliJ]
workspaceの使い方がわからない。名前空間はどうなっている?
debugボタンで実行すればbreak pointが動いた。
イマイチ効率の良い使い方は分からない。

==== Etc. ====
[全体を振り返って]
予習をしていたこともあり、内容はそんなに難しくなったので、初めてのMOOCに丁度良かった。
あまり難しくない割にはAssignmentは結構時間が掛かってしまった。
講義はもう少し詳しく見た方が良かったかもしれない。
ポイントは押えたつもりだが、個々の例題などは追い切れていない。

プログラムを実行するという事は「置き換え」だという事が印象に残った。
置き換え回数が計算量になる。
副作用が無ければどの部分からどの順序で置き換えても良い。
これが関数型プログラミングと並列計算の相性の良い所。

==== Log ====
2014/06/09 00:50 Lecture
2014/06/10 00:30 Assignment
2014/06/11 00:50 Lecture
2014/06/13 00:20 Assignment
2014/06/14 04:30 Assignment