Purely Functional Data Structures読書会 第3回

勉強会 Program Haskell

12/17 に、Purely Functional Data Structures読書会 第3回 に行ってきました。

  • 開始前

Mac (Lion) のデスクトップ増やす:
Mission Control から カーソルを右上の方にやると「+」が出てくる。
押すと増える。


Lion から操作が変わった部分は、わりと前から使っていたユーザを苦しめてるっぽい。

  • 練習問題回答
    • 3.2 LeftistHeap の insert を merge を使わずに実装する

http://blog-ja.intransient.info/2011/11/leftistheap-in-haskell.html


こういうのって、Coq で書いていれば、どんな入力に対しても、
元のやつと新しく作ったやつが同じ動作をするとか証明できていいなと思った。


Heap Tree はバランスしてない方が速いことが多いらしい。
(makeT y b (insert x a) の方が速い？)


quickCheck の代わりに verboseCheck を使うと、実際に入れられた値が分かる。
100個くらいだと、あまり信頼できない。
(リストとかだと、割と空リストが多い)

    • 2.6 UnbalancedSet を基に FiniteMap を作る

OCaml で。
val とか with type とか。ちょっと微妙らしい。

functor は最近ではあまり使われてなく、first class module が使われてるらしい。

    • 3.5 BinominalHeap の findMin を removeMinTree を使わずに作る
findMin ts = minimum $ fmap root ts

な感じ。
minimuBy を使うともっといい感じにできるかも。


OCaml:
比較演算は勝手にできるようになるらしい。
(デフォルトで deriving Eq, Ord 的な)
deriving もあって、既存の型に Show 的なものをつけたりすることも出来る。
タプルの括弧が省略できる。(, があればおｋ)
カリー化された関数は、タプルにしてパターンマッチというのをやることが多いらしい。


テストのお話 by kazu_yamamoto
スマートズーム : 環境設定／ユニバーサルアクセス／視覚／ズーム機能／オプション の一番下「スクロールホイールと修飾キーを使ってズーム」
model check : 動くものが既にあるときに、それと同じものを返すことを確認する
quickCheck を手動でやらず、テストフレームワークを使うと楽。


test-framework (利用例)
https://github.com/kazu-yamamoto/bst/blob/master/test/Test.hs


TestGroupGenerator
http://hackage.haskell.org/package/test-framework-th

    • 3.6 BinomialHeap の rank を Tree の外に出して作る

https://github.com/seizans/pfds/blob/master/2/BinomialHeap.hs
型の定義をうまくすると、一部の関数を除いて殆ど同じにできるらしい。

    • 3.9 リストから Red-Black Tree を作る関数 fromOrdList を作る

https://github.com/shtaag/Haskell/blob/master/pfds/RedBlackSet.hs
参考：http://t.co/P3SiwhRE
資料：http://www.slideshare.net/ShigekazuTakei/pfds-ex3-9


Red-Black Tree は、赤いエッジを心眼で見なくすると、2-3-4木 (完全バランス) らしい。
2-3木でも完全バランスするらしく、それだと赤は左だけで出来る。
2-3木を普通に作ってもいいかも。


Red-Black Tree への insert は、最初赤で入れると、
黒の制約そのままで、赤の制約に引っかかる。
黒の制約を満たしつつ、バランスしていくと、root に赤が来て、
それ以外はうまくいっている状態になる。
あとは、root の色を黒にすれば、完成。らしい。


Red-Black Tree の制約は緩く、多くの実装がある。
アルゴリズム・イントロダクションでは、叔父のノードまで見て
8パターンの balance になっている。


B木は 2-3-4木/Red-Black Tree と近い。(同じ？)


2-3-4木:
各ノードが、
1つの要素と2つの子/2つの要素と3つの子/3つの要素と4つの子
のどれかである木。 完全バランスしている。
Red-Black Tree の赤のノードを親にくっつけると、2-3-4木が出来る。

    • 3.10 balance 関数を右と左に分けて作る

https://github.com/kazu-yamamoto/llrbtree/blob/master/Data/RBTree/Original.hs

    • 3.4 (b) LeftistHeap を weight-biased にする

makeT だけ書き換えてできる。

    • 3.4 (c) makeT を使わないようにして、単一パスの merge を作る

top-down にする。末尾再帰みたいにする。
次回へ。

    • 3.8 サイズ n の深さは 2 * floor(log (n + 1)) 以下になることを証明

https://docs.google.com/document/d/1MfH9-GXHzemYUaM3LagyBcN12GdyPPxeyvJ3VyQAoAo/edit?hl=ja&pli=1
帰納法で証明するといいらしい。

  • 4章解説

OCaml の lazy
https://github.com/master-q/readPurelyFunctionalDataStructures/tree/master/LazyEvaluation
遅延リストの中身が取得時に評価されてしまうかも。


Haskell すばらしい。
遅延リストはいいぞ。


Haskellで無限フィボナッチ数列を作る

fibs = 1:1:zipWith (+) fibs (tail fibs)

とか

fibs = 1:scanl (+) 1 fibs

とか。

fibs = 1:zipWith (+) fibs (tail fibs)

ってやると2つめが以降が返って来ないとか。

  • 帰り

@seizans と @S1E11 と中華食べた。
Haskell 触った後 Java 触ると Java の書き方が変わったり Java が残念に感じるよねって話とか、
Java は Eclipse が型推論してくれるんだ(ｷﾘｯ)とか、
Eclipse の設定やショートカットとか、
お仕事の話とか。

  • 次の日

まとめようと思ったけど睡魔に負けた・・・