2010年12月12日 日曜日
■ [メモ]ええと(1)...
数学って美しい世界だと思ったら、かなりカオスだなぁ...
それぞれな分野では綺麗にまとまってるのだが、一段上から見下ろすと全くもってカオス。M$ Windowsの世界と共通するグチャグチャさがあった...
とりあえず、圏論から地道にやっているのだが、A -> Zを調べようとすると、A -> B -> Zと、Bの概念が必要になったリする。A -> Bを理解して、さぁ、B -> Zを調べると、実はB -> C -> Zで、Cの概念が必要になる。で、順番にD、E、F...とたらい回しにされるのだが、その内に以前のAとかBに行き着いて循環参照になるのでは...という不安...
まぁ、厳密にはやる気ないし、やれもしないから大体わかればいいんですけど...
とりあえず、現状でこんな感じ...
Arrow -> Monad -> 圏論 -> 関手 -> 自然変換 -> 米田の補題-> Hom-functor -> 埋め込み -> bifunctor(双関手) -> デカルト閉圏 -> モノイド積(テンソル積) -> 随伴関手 -> 普遍性 -> 始対象とかになって先が見えなくなってきた...
で、とりあえず基本から学ぼうということになって線形代数をやる。Hermite行列までやって、これどっかで見たなぁ..と思ったらシュレディンガー方程式だっけ？？？
ちょっと物理の世界を覗き始めたら、ハミルトニアン、ラプラシアン、ラグランジアン、ヤコビアンとか出てくるのだが覚えていない。ただ、どの概念も圏論の関手と随伴性でほぼ説明できそうだというのはわかるのだが...
■ [メモ]ええと(2)...
で、終わりそうにないから、とりあえず何がしたかったのかを思い出してみると...
「上手く随伴関手のペアを見つけて、そこからMonadが作れるけど、もうちょっと上手くやると、Arrowが作れるんじゃないか」ってことで調べ出した。実際に理解してはいないけど、「Generalizing Monads to Arrows」のはるか以前からその手の研究はされているようだ...
つか、上手い具合に対応する自然変換が２つ決定できればいいのだよ...
まぁ、でも、それなりにはわかってきて、Arrow則の(1)～(3)は普通に圏の射であるための要請。(4)～(8)は一意的には決められないとは思うけど、双関手であるための(モノイド積(テンソル積)の結合性に関する)要請っぽい。要は、
(AⓧB)ⓧC == Aⓧ(BⓧC)
なら、(>>>)で繋いだ場合とアロー記法で書いた場合が一致する...ということでいいと思う。まぁ、Arrow則もMonad則と同様にアロー記法を成り立たせる基盤となっていることだけ再確認した...
■ [メモ]ええと(3)...
で、Daniel Marinus KanというMIT名誉教授が出てくる...
英語版のWikiに簡単な人物説明があった。一部を引用すると...
His most famous work is the abstract formulation of the discovery of adjoint functors, which dates from 1958. The Kan extension is one of the broadest descriptions of a useful general class of adjunctions.
よくわからないけど、随伴関手のペアって、そんなに簡単に構成できてしまうものなのか。カン拡張は使えるかどうかはともかく、Haskellのライブラリにあるなぁ...
謎なライブラリだと思っていたけど、実は役に立つかもしれない気がしてきた。しかし、それまでに基礎学力をつけないことには登ってもすぐに落ちてしまう...
■ [メモ]やば、キャミバ様が面白すぎる...
キャミバ様はここに居られます -> 2010-12-10 - Oh, you `re no (fun _ → more)
多分、CodeForcesのBeta Round 5(C)のLongest Regular Bracket Sequenceみたいなことをやりたいのだとエスパー。この問題は基本Ο(N)なはず...
遅いコードを木人形(デク)と称し、そのコードをTopCoder的な簡潔で速いコードに仕上げるまでの過程が面白おかしく描かれている。OCamlな人でなくても十分に楽しめる内容...
つか、言語云々より、アミバ様をどれだけ理解しているかの方が重要...
因みにOCamlのCamlは、Categorical abstract machine languageの略らしい。OCamlは全然知らないけど、F#は一通りやったことがあるので大体わかる...
OCaml/F# Haskell --------------------------------------------- let(rec)(and) let match x with case x of Some/None Just/Nothing fun x -> f x \x -> f x
で、このエントリに関しては理解できるかと。文法的には関数型に分類されるだけあって似ている。評価がデフォで遅延か正格かくらいしか差がわからないのだけど、一般にOCamlが生成するコードは速い...らしい...
しかし、キャミバ様、マジ天才だわ...
■ [メモ]米田の補題...
漢字間違えてたので直した。MS-IMEと言い、Googleと言い、あるレベルを超えると逆に使い難くなってゆく...
発表されたのが１９５０年代前半？？？
カン拡張に含まれてしまうような概念だと思うから、１９６０年以前であることは間違いない...と思うのだが...
拡張Functorライブラリを使って、埋め込み職人になるのが当面の目標で、とりあえず、Arrow(正直、Arrowでできないことはない)とKan Extension系のライブラリを使えるようになろう...
Functorと自然変換から高階Arrowまで、何でもアリ、つか入力が高階になってきた。基本的に入力が射(関数、関手)で、出力もそれ相応みたいな...キモイ...
あと、「なぜ関数プログラミングは重要か」を読んだ。つか、John Hughes教授(QuickCheckの開発で有名)の論文(？)があまりに数学っぽくないから、ちゃんと数学科とか出てるのか調べたけど、経歴がよくわからない...
つか、数学系の出なら、多分、ArrowCircuitのdelayとか思いつかないはずで、逆にArrowColoringとかArrowEmbeddingみたいな変なクラスを作りたくなるはず(数学系の人は面白くて、グラフを見つけると何故か色を付けたくなったりとか、何かが普通と違う)...
経験的にだが、Haskellで何かを説明するような記事は、その内容が平易なら大体間違っている、か書いた人が間違ってることに気が付いていない...ことが多い(私も何度も嘘を書きました...すいません)。ウンザリするくらいコードが多かったり、読みたくなくなるような文章ほど意外とまともだったりするわけで、新規参入の敷居が異様に高い...
言語仕様自体はムズいわけじゃないけど、情報が少ないし、あってもそれが嘘である確率が結構高くて苦労する。入門記事みたいのは多いのだけど...
で、「なぜ関数プログラミングは重要か」ではfoldl(r)、iterateによる高階化と遅延評価の例としてゲーム木(？)のサンプルがあるけど、特にC++でも問題なく実装できると思うし(入出力が絡むと逆にC++の方が楽に書ける)、関数型言語でないと難しいという例には思えない...
ただ、２５年前にこれが書かれてるってのはスゴイことかも。神よ、もっと光を...
(たまには批判的なことも書いてみた...)