#format md #acl +All:read # OCaml演習第三回メモ もうちょっと基本的なこと書く方が需要あるのかな… ## 赤黒木 単なる二分探索木でも十分だし、最悪連想リスト書いても良いかと思いますが、平衡取りたくなるのが人情というものなので。 Algorithm with Pythonとか適当な教科書とかの赤黒木の説明を見た上で、ボトムアップに書くことを意識すれば、多分書けることは書けます。deleteを、削除済みマークをつける実装でなく、まじめに書くなら大変かと思いますが。ぼくがSchemeでdelete以外を書いたときは、2-3-4木として操作することをイメージして書くとまだ混乱せずに書けました。バリアントとパターンマッチがちゃんとできるOCamlだとそもそもそんな混乱しないかも。他の平衡二分木としては、Haskellでアデ構に出てきた2-3木を書いたコードはにあります。 ただ、 一般的な赤黒木の実装よりももっと簡潔な実装も存在します。Chris OkasakiのPurely Functional Data Structuresという本に元々書いていて、[永続二色木 - あどけない話](http://d.hatena.ne.jp/kazu-yamamoto/20111012/1318389975)に解説があります。二つの赤ノードが連続した際に、祖父から見てどの向きに赤ノードが二つできているかの4通りの場合分けだけで書くことができます（前述のブログ記事には、黄の☆と緑の☆の2通りだけが示されています）。またRalf Hinzeの[Constructing Red-Black Trees](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458)という論文で突っ込んだ考察がなされているようです。 なお、deleteを削除済みマークをつける実装で行なっても、木の全体の半分が削除済みになったときに新しい木を一からつくるようにすれば、木のバランスはオーダーとして悪くはならないし、deleteのならし計算量は木の要素数をNとしてO(logN)で済みます。これをちゃんとやろうとすると、木の再構築はO(N)で行わないといけないことに注意が必要です。木の要素を値として小さいものから大きいものへ走査するのは、深さ優先探索でO(N)で可能です。木の要素数を保持していれば、新しい平衡の取れた木を構築してやる作業もO(N)でできるはずです。 Purely Functional Data Structuresを読みたい人がいれば、ぼくに言ってくれれば貸します。 ## 多相再帰 スライドの内容がヒントになっているので考えれば分かるとは思いますが（授業は出ていなかったのでヒントとなるような口頭説明があったかは知らない）、Polymorphic Recursionでググればそのままの解説が出てきます。 ## GADT GADTとはなんぞやは、[Generalised algebraic datatype - HaskellWiki](http://www.haskell.org/haskellwiki/GADT)が一番分かりやすいと思います。イントロダクションになるような論文も結構あるとは思いますが、全く読んでないので何が良いかとかは分からないです。 EqクラスのLiftの実装には、first-class moduleという機能を使うようです。Lift以外は、ちょっと考えれば全員知っているはずの知識だけで副作用や例外を使わず実装できます。Liftを除く実装を考えるだけでも、関数型プログラミングの良い頭の体操になりそうです。ちなみに、Cで書いた関数を呼び出す機能を悪用すれば、任意の型にキャストすることが可能っぽいので、その方向から実装することも多分可能です。 参考となるようなWebサイトは、[OCaml 3.12のマニュアルのFirst-class modulesのセクション](http://caml.inria.fr/pub/distrib/ocaml-3.12/ocaml-3.12-refman.html#htoc109)とか、[More expressive GADT encodings via first class modules|ocaml.janestreet.com](https://ocaml.janestreet.com/?q=node/81)とかです。 なお、課題で書いたExprに対するGADTの実装だけなら、実はreflだけで可能な気がします。evalの型を`'a expr -> 'a`に変更すれば、symmとapplyが必要になるかと思いますが。任意の型でパラメタライズができるかのような型付けをしつつ、('a int) equalという型を持つ値はreflでしか作り出せないので'aはどうしてもintになる、という制約を使って、コンストラクタによって異なる型を埋め込むのを実現してやろう、という感じですかね。この辺あやふやなので、勘違いだったら指摘してください。 existential type（存在型）をめぐって混乱したことも後で書くかも。 ---- [[FLProgClassCategory]]