Workshop/ReadPFDS/1
調整
Purely Functional Data Structures読書会 第1回 - PARTAKE
スケジュール
↑のpartakeに書いた。
資料
- Weight-Balanced Trees
- [2章について @master_q](http://www.slideshare.net/master_q/readpfds1)
- Leftist Heap - 言語ゲーム
- [PFDSの例をOCamlで Functor使って実装してみた @khibino](https://github.com/khibino/pfds)
- “Efficient sets: a balancing act” をもとに DData というライブラリを作成。（現在は containers パッケージに収録）
- “Trends in Functional Programming 2011” の “Adams’ Trees Revisited - Correct and Efficient Implementation”
- Matthieu Sozeau :: Dependent Finger Trees in Coq
- Matthieu Sozeau :: Coq stuff
- sneezy.cs.nott.ac.uk/darcs/DTP08/slides/Matthieu.pdf
- 2-3 フィンガーツリーを図で説明
- Animated working of a Two-Three-Four tree - a kind of B-Tree
- Haskellの正格フラグについて
- 優先度付きキューの実装に FingerTree を使 …
- この辺りの議論は Trac ではなく librari …
- HackageDB: PSQueue-1.1
- GHC/Event/PSQ.hs
- ちなみに pqueue パッケージの実装は binomial heap ベースです。
- Missing method: How to delete from Okasaki’s red-black trees
- Chris Okasaki ファンなら、EdisonCoreも見ておくと良い
- 永続二色木 - あどけない話
議事録
録画と写真
Weight-Balanced TreesのパラメータをCoqによる証明で決定する話 @kazu_yamamoto
Coqを学ぶ必要性が理解できた。 今は型を使ってアルゴリズム同士の界面のインピーダンスミスマッチを防止しているが、 アルゴリズムそのもののエラーチェックをすうためには証明が非常に重要。
2章 @master_q
「Persistenceとはgitのようなバージョン管理システムと似ている」とブチあげたが、あえなく撃沈。。。 orz
3-1章 Leftist Heaps @master_q
Haskellerにとってはすんなり理解できるWebページ。さすが @propella さん。 @master_q は時間がなくって資料作成をサボったらしい。
3-2章 Binomial Heaps @imsuten
ツリーがリストになっていて、リストの1要素がbitのように振る舞うのが面白い。
3-3章 Red-Black Trees @kazu_yamamoto
Persistenceな実装と破壊的な実装では異なる赤黒木ができる。 赤黒木はツリーが一意に決まるような規則ではないので、解釈によって異なるツリーができあがることはある。 Persistenceは非破壊はので、関数型と相性が良いことがメリットだが、 この例ではさらにアルゴリズムが単純化できるというメリットもおまけで付いてくることがある、 ということを学んだ。
ネタ案出し
とりあえず「演習問題の答あわせ+ネタ発表(あれば)」という勉強会スタイルにすることにした。
次回
演習問題によって難易度がばらばらなので、わからないことは Chaton haskell-ja で聞いてください。
