Purely Functional Data Structures読書会 第4回

勉強会 Program Haskell

1/21 に、Purely Functional Data Structures読書会 第4回 に行ってきました。

まとめ的な： http://wiki.haskell.jp/Workshop/ReadPFDS/4

  • 3.4 (c) (d)

@khibino
前回末尾再帰になっていなかったから、CPS変換して末尾再帰にしたらしい。


なんかいきなり継続の話に。
任意の場所で継続がとれる、call/cc スタイルの CPS だけを CPS という人もいるらしい。

  • 3.10 (b)

@imsuten
http://blog-ja.intransient.info/2012/01/red-black-tree-balance.html


以下の balanceL も見ておくといい
http://hackage.haskell.org/packages/archive/containers/0.4.2.0/doc/html/src/Data-Map.html#Map

  • 4

@master_q
4章をOCamlで書く
やる気のある資料： http://www.slideshare.net/master_q/pfds-4ocaml


$-notation の代わりに lazy キーワードを使う
lazy の後は気持ちよく全部括弧でくるむ！
　　(括弧が嫌なら begin/end も使える)
Lazy.force で取り出す


カリー形式だと一気にマッチできないので、タプルを使うことが多い (ML系)

fun plus($m, $n) = $m + n

↓

	let plus (lazy m) (lazy n) = lazy (m + n)
    • m + n の計算は遅延される
    • m と n は評価されてしまう
fun lazy plus ($m, $n) = $m + n

=

fun plus (m, n) = $case (m, n) of ($m, $n) => force ($m + n)

↓

	let plus m n = lazy (match (m, n) with (lazy m, lazy n) -> m + n)
    • with の先でマッチした変数名を m, n として、そのスコープでもとの変数を隠すこともある
    • m, n の中身をほどくのも、その足し算も遅延される
    • Stream の型
      • susp の代わりに Lazy.t を使う


トップレベルの let はシャドウイング出来る
OCaml の文法は気違い (by kazu_yamamoto)

  • 4.1

@seizans

fun dropA x = $case x of
 | (0, s) = force s 
 | (n, $Nil) = force $Nil
 | (n, $Cons(x, s)) = force (dropA(n - 1, s))

fun dropB x = $case x of
 | (n, s) = force (
    let fun
      dropB' (0, s) = s
      dropB' (n, $Nil) = $Nil
      dropB' (n, $Cons(x, s)) = dropB' (n - 1, s)
    in dropB' (n, s)
  )

force を中に入れたり外に出したりはできる。
n をばらしたとき、 force ($ ...) がいくつか出来るが、それは簡約可能。

  • 4.2

@rf0444
遅延リストに対して insertion sort を作って、その計算量がソート済み先頭k要素を取ってくるなら、O(n*k) になるっていうの。
最初 Coq で計算量の証明をしようとしていたが、・・・挫折。
(跡地： https://github.com/rf0444/coq/tree/master/pfds)
前日に Haskell で作って、挙動を追うと、・・・あれ？挿入ソートというよりは・・・バブルソートの挙動になってる！！
https://github.com/rf0444/haskell/tree/master/study/PFDS/C4


ソート超奥深そう。
遅延リストの挿入ソートの挙動がバブルソートっぽくなるのは、アルゴリズムのなんとか変換とかいう概念があるらしい。
homomorphic sort でぐぐると幸せになれるらしい。
http://d.hatena.ne.jp/kazu-yamamoto/20110913/1315905876

  • 5

@senzans
償却計算量、銀行家と物理屋の手法
ならし解析


アルゴリズムイントロダクションを読んで、比較すると面白いらしい。
用語対応： https://twitter.com/#!/seizans/status/158462657807138816


銀行家の方法は、正格/遅延リストで、積み立て/借金の方法で計算量を出す。

  • 次回

引き続き 5章解説。
となりで @S1E11 が頑張って資料作っていた。