The End of Start Haskell
1/28 に、第6回 スタートHaskell に行ってきました!
また1週間かかってしまった・・・遅延評価だから仕方がない (キリッ
- 12章 遅延評価 解説
最内簡約
(Leftmost) Innermost evaluation
内側から外側、左から右
関数適用より先に引数が評価 引数の値渡し (call-by-value)
最外簡約
(Leftmost) Outermost evaluation
外側から内側、左から右
引数の評価より先に関数が適用される 引数の名前渡し (call-by-name)
(値渡し、名前渡しより最内、最外のほうが分かりやすい)
(ここで遅刻組到着)
(大量の参加者が遅延評価されている)
(Haskell は) Lambda の中は簡約しない。
Lambda は関数定義
Lambda 計算に基づいているので、Lambda 内は弄らない
コンパイル時に最適化される話と、実行時にどうやって簡約されるかは全く別の話
値渡しでは停止しない式も、名前渡しだと停止することもある。
停止する評価戦略があれば、名前渡しは必ず停止し、その戦略時の評価と同じ結果を返す
簡約回数
元々一つの式なら、1度だけ評価してくれる (式の共有)
同じ式が2つ出てきただけなら、共有してくれない
変数に抽出すると、その変数が評価されるとき、1度だけ評価してくれる
call-by-name + 式の共有 = call-by-need = lazy-evaluation
木の簡約ではなく、グラフ簡約になる
共有部分が出来るので、木構造が崩れる
部品プログラミング
データと制御を切り離す
無限データを定義、どれだけ使うかは制御側で
無限データ自体は、遅延でなくても、再帰的データ構造が使えれば作れる
正格適用
$! (ダラバン) 演算子
$ 演算子の、右側を先に評価する版
空間効率が向上することがある
しないこともある
seq 関数を使って定義される
foldl とかは正格が良さげ
foldr とかは遅延のが良さげ
Weak Head Normal Form (WHNF)
参考: http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/?ST=ittrend&mkjt&P=2
Normal Form : これ以上簡約できない式
Normal Form と見なされるための制約を緩めたものの一つが、WHNF
Haskell は、式を WHNF に簡約する
例を考えるときは、Lambda より List の方が分かりやすい
- 12章 演習問題
-
- 1, 2, 3
@choplin
https://github.com/choplin/start_haskell/blob/master/12.lhs
-
- 4
@shokos
fibs = 0:1:[uncurry (+) (a, b) | (a, b) <- zip fibs (tail fibs)]
uncurry なしで
fibs = 0:1:[a + b | (a, b) <- zip fibs (tail fibs)]
でもできる。
リスト内包表記なしなら、
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
とか、パターンマッチを使って、
fibs@(_:tfibs) = 0 : 1 : zipWith (+) fibs tfibs
とか書ける。
自分は、
fibs = 0 : scanl (+) 1 fibs
が好き。
-
- 5
@dekosuke
fib n = head $ drop n fibs fib1000 = head $ dropWhile (<= 1000) fibs
!! を使って、
fib n = fibs !! n
でもいい。
-
- 6
@beketa
repeatTree x = xTree where xTree = Node xTree x xTree
とか。
- 13章 プログラムの論証 解説
@kawamoto
関数定義を、逆に置換することも出来る
パターンマッチを使った定義は、それより上の定義に一致しないという条件が付くので注意
関数の性質から定義を導く
天下り的に定義を与えるのではなく、性質を満たすことを証明することで、その定義を導く
確立できれば、「証明駆動開発」も夢じゃない!?
既に効率の悪いものがある場合、引数を一つ増やした版を作って、その2つの関係を証明していくことで、引数増やしたの関数定義を導く
引数増やした版の関数を使って元の関数を定義すると、効率の良いものが出来る
証明したい性質・関数をうまく一般化してやると、証明が簡単になり、また導かれる関数の効率がよくなることがよくある
CPS 変換して証明して、元の定義は cont に id 入れるのと似ている
末尾再帰になって効率上がるし。
フィボナッチのときも、「n の時に成り立ち、かつ n + 1 の時に成り立つ」で証明した。
参考文献 30: http://homepages.inf.ed.ac.uk/wadler/papers/vanish/vanish.pdf
($) と (.) の話: http://d.hatena.ne.jp/kazu-yamamoto/20100702/1278036842
- 13章 演習問題
自分が Coq でやった分: https://github.com/rf0444/coq/blob/master/start_haskell/13.v
-
- 1
重複のあるパターンで定義されている関数
-
- 2, 3, 4, 5
ひたすら数学的帰納法が続く。
-
- 7
@master_q
http://www.slideshare.net/master_q/20120128-start-haskell6
背景のイカwww
-
- 8
@sat0_da
Coq 紹介
change で 指定された形に簡約する
-
- 9
@senzans
https://github.com/seizans/exercise/blob/master/start_haskell/ch13/ex9.lhs
-
- 10
@beketa
- LT
QuickCheck の話
性質検証
性質を書いて、ランダムチェックできる
template haskell を使って、prop_ から始まるテストを全て実行できる
生成されたランダム値を出力することもできる
参考: http://itpro.nikkeibp.co.jp/article/COLUMN/20080304/295346/
shpider package
http://hackage.haskell.org/package/shpider-0.2.1.1
クローラ
使って、食べログにばんくらった。
HaskellWiki をクロールしてみた
http://d.hatena.ne.jp/Dekosuke/20120108
OpenGL を使ってみた
https://github.com/shtaag/Haskell/tree/master/opengl
http://taketoncheir.hatenablog.com/entry/2012/01/07/232345
最終的にはゲームを作りたい
モナディウス的な
gloss package が便利らしい
http://hackage.haskell.org/package/gloss-1.0.0.1
逆ポーランド記法の電卓を作った
https://github.com/yunomu/exercises/tree/master/dc_haskell
Real World な Haskell
浮動小数注意
演算で投げられる例外に注意
ArithException か SomeException か
Hoogle をローカルで使う
Hoogle: http://www.haskell.org/hoogle/
入れ方
cabal install hoogle
わりと時間かかる
hoogle data
やり方
hoogle 調べたいやつ
ghci 中で :hoogle
~/.cabal/bin/hoogle server
ポート80で見れる
GHCi debugger
http://d.hatena.ne.jp/khibino0/20111212/1323680441
Haskell とテストと BDD
http://d.hatena.ne.jp/kazu-yamamoto/20120112/1326335764
ぶっちゃけて言うと、BDD は TDD
名前にテストって入ってると設計的な見方が軽視される的な
haddoc: doctest の Haskell 版的な
quickcheck 的なこともしたい
test-framework 使いたい
quickcheck 自体を document の方に書きたい
haddoc 拡張されるかも!
Haskell の勉強会
http://wiki.haskell.jp/Workshop
- 次回
多数決的には Real World Haskell か?
Learn You a Haskell for Great Good (日本語版!?) になるとか。