From a Far East Island

2007-02-16

[]Haskel モナドの解説 from 2ch

735 :デフォルト名無しさん :2007/02/15(木) 00:11:39

>>733

3行で説明するのは俺には無理.

まず定義5.これは実際に手を動かすと見えてくるので,

具体例でやるのが良いと思う.以下はその pdf にもある例.

1. リスト函手

・型 A に対し T A は A のリストを作る:

  T A = [A]

関数 f :: A -> B に対し T f :: [A] -> [B] は次の関数を作る:

  T f = map f

・μ_X は X 型のリストのリストをならして X 型のリストを作る:

  μ_X = concat

・η_X は X 型の値 x からそれだけからなる [X} 型のリスト [x] を作る:

  η_X = singleton = (:[])

これらを図に代入して,ちゃんと可換になることを確認するよろし.

736 :デフォルト名無しさん :2007/02/15(木) 00:18:09

こっちも同様に確認するとμ,ηの雰囲気がより分かるかも.

2. Maybe函手

・型 A に対し T A は Maybe A を作る:

  T A = Maybe A = Just A | Nothing

関数 f :: A -> B に対し T f :: Maybe A -> Maybe B は

  (T f) (Just a) = Just (f a)

  (T f) Nothing = Nothing

・μ_X は Maybe (Maybe X) を Maybe X にする:

  μ_X (Just (Just x)) = Just x

  μ_X (Just Nothing) = Nothing

  μ_X Nothing = Nothing

・η_X は X の値 x を (Just x) にする:

  η_X x = Just x

737 :デフォルト名無しさん :2007/02/15(木) 00:49:19

やっと分かった!

drop 5もreverseもnullも自然変換で、

map succやallは自然変換でないと。

前者は構造のみを扱い、後者は要素が絡んでいることを反映しているのか。

これ考えた奴は天才だな。

738 :デフォルト名無しさん :2007/02/15(木) 00:50:21

次に定義6.こっちも具体例が条件を満たすことを確認すると見える.

1. リスト函手.これはありがたみが分かりづらい.

・f* = flatten . map f

2. Maybe函手.

・f* = Just . f

Maybe がこれでハッピーなのは,次の具体例を考えると分かる:

「バッグからアドレス帳を取り出し,

 今日誕生日の人を探し,携帯電話を取得する」

これを関数合成で次のように書けるとうれしい:

 getPhone . findBornToday . getAddressbook

ただ,各関数の自然な型は

 getAddressbook :: Bag -> Maybe Addressboo(もってないかも)

 findBornToday :: Addressbook -> Maybe Person(いないかも)

 getPhone :: Person -> Maybe Phone(もってないかも)

なので合成ができない.そこで,* を使って

 getPhone* . findBornToday* . getAddressbook

と書いてやると型があってハッピー.Haskell ではこれを

 getPhone <<= findBornToday <<= getAddressbook

と書けるようになってる.

739 :デフォルト名無しさん :2007/02/15(木) 01:06:12

定義5の可換を具体例で示すことはできた。

が、『μが結合則、ηが恒等元の役割をする』というところがピンとこない。

なにとぞ、悟りの光をお与えください。



740 :デフォルト名無しさん :2007/02/15(木) 01:29:09

結合則」という意味:

 左側の図で上側を通る計算はμを中置記法で書き,

 TμT = T と簡約しないでおくと

  T T T A --> (TμT) T A --> (TμT)μT A

 となる.同様に下側を通る計算は

  T T T A --> T (TμT) A --> Tμ(TμT) A

 となる.これが(任意の A について)等しいのだから,雰囲気は

  (TμT)μT = Tμ(TμT)  …代数で言うところの結合則

「恒等元」という意味:

 右側の図で左側の三角形の真ん中を通る計算は

 ηT = T T と簡約しないでおくと

  T A --> ηT A --> ημT A

 右側の三角形の真ん中を通る計算は

  T A --> Tη A --> Tμη A

 これが恒等写像 id_TA に等しいのだから,雰囲気は

  ημT = Tμη = T  …代数で言うところの恒等元,単位元

741 :デフォルト名無しさん :2007/02/15(木) 03:45:58

>>740

泥ス 結合法則のほうは分かったw  中置記法が味噌かよwww

中置記法で書くと確かに結合側に見えるw

麻呂は前置記法で書いていたので、どう見ても結合法則ではなく可換を意味しているようにしか

見えなかったでおじゃるw


恒等元のほうは、まだ分からんw

ηだけで恒等元??  (ημ)で恒等元? 

でもサ変と右辺でημとμηでひっくり返っているし

もう3行ばかり解説頼むw


742 :デフォルト名無しさん :2007/02/15(木) 07:50:31

>>741

一般に,二項演算 * に対して e が恒等元であるとは

任意の a に対して e * a = a * e = a を満たすことを言う.

μを中置記法で読めば,最後に出てくる式はこれと同じ.

743 :デフォルト名無しさん :2007/02/15(木) 09:20:05

>>740

凄い! なんかわかった気になる。

そうか、μをfunctor間の演算とみなせばよかったのか。

ところで>738の例で

Maybe functorがf* = Just . f

とあるけど、これでfindBornToday*が

Addressbook -> Maybe Person

から

Maybe Addressbook -> Maybe Person

になるんだろうか?

fをもちあげないといけない気がするんだが…

744 :デフォルト名無しさん :2007/02/15(木) 10:25:48

>>743

そのとおりで,こちらのミス.手抜きをしたのがいけなかった.以下が正しい.

f* (Just x) = Just (f x)

f* Nothing = Nothing

745 :デフォルト名無しさん :2007/02/15(木) 10:35:57

ああまたミス.f* (Just x) = f x,f* Nothing = Nothing.起きたばかりだけど寝てくる.

746 :デフォルト名無しさん :2007/02/15(木) 18:09:27

lispとどっち勉強するか迷ってます

lispよりも強力なのがhaskellってことでいいのでしょうか?

強力というのは最小限の手間で複雑な処理がかけるという意味で




747 :デフォルト名無しさん :2007/02/15(木) 18:40:24

>>746

迷ったなら両方やっとけば。

Lisp風呂敷。なんでもリストでつつんでしまう。良く言えば柔軟。悪くいえば節操がない。

Haskellはディナー用食器セット。テーブルマナーがわかっていれば心地良い。

748 :デフォルト名無しさん :2007/02/15(木) 18:56:11

>>747

Haskellはディナー用食器セット。テーブルマナーがわかっていれば心地良い。

でも調理は自分で、でも何故かアレルギー反応する人がいるのがおもしろい。



749 :デフォルト名無しさん :2007/02/15(木) 19:59:31

昨日は詳しい人がいたのね。

HaskellMonadって、実はKleisliの方が近いんじゃないか、と思うんだけど、

何でMonadと呼ばれているんだろう?

(T,η, *)と(M, return, flip (>>=))が対応してるのに対して、(T, η, μ)とは

間接的にしか対応してないのに。Monadなんて使わなければ関連する定義

も1つ減って幸せな気がする。

750 :デフォルト名無しさん :2007/02/15(木) 22:08:19

対象→例えば数字だったり、式だったり、式+式だったり

群  →対象の集まり

圏  →対象と射の集まり

これで認識あってる?

751 :デフォルト名無しさん :2007/02/15(木) 22:21:00

モナドは函手の間の演算だってそういうことですか・・・。

752 :デフォルト名無しさん :2007/02/15(木) 22:30:13

>>750

数学の用語としてだったら、群は間違ってる。

群は、可逆な演算の定義された集合の事(厳密な言い方でないけど)。

例えば、整数の集合に足し算と引き算を定義すれば、群である。

圏は一応あってると言っていいと思う。

753 :デフォルト名無しさん :2007/02/15(木) 22:33:50

可逆という言葉がわからん

集合という言葉の定義がわからん

754 :デフォルト名無しさん :2007/02/15(木) 22:39:02

群はモノイドでかつ任意の元に対して逆元が存在するもの。

755 :デフォルト名無しさん :2007/02/15(木) 22:40:22

http://ja.wikipedia.org/wiki/%E5%85%AC%E7%90%86%E7%9A%84%E9%9B%86%E5%90%88%E8%AB%96

756 :デフォルト名無しさん :2007/02/15(木) 22:48:49

やっぱりボチボチと圏論わかってきてるひと増えてるんだね。

でも、やっぱりよくわからのだがこれ一体なんの役に立つんだ?


757 :750:2007/02/15(木) 22:50:04

たぶん、オブジェクト指向のようなものだと思うんだが

758 :デフォルト名無しさん :2007/02/15(木) 22:55:56

>>749

一般にプログラミング上の専門用語は、

「寓意的・即物的」であることが好まれるからだろう。

"Kleisli" なんていう、

どう読めばよいのかも分からない人名をつけるよりも、

"Monad" なんて単語のほうがずっとイメージしやすいしね。

この特徴は、プログラミングが「科学」ではなく、

まさに「工学」であることの証拠のように思える。

ていうか、ここら辺はむしろ「科学」のほうが異常なんだと思う。

発見者(又は、偉大な業績を残した先人達)の学問上の

功績を称えるために、発見したものに対して

その人の名前を冠する、という悪しき慣習のために、

新しい概念に対して本当にふさわしい名前をつけることが

出来てないんだよ。


759 :756:2007/02/15(木) 22:56:08

>たぶん、オブジェクト指向のようなものだと思うんだが

なるほど。

でも、だとしたらコストが高すぎる。一体どれだけ時間かかるんだ。

ていうか、いい加減コーディングスタイル確立してくれ。

というわけで偉い人がんばってくれ。

760 :デフォルト名無しさん :2007/02/15(木) 23:01:46

>>758

Haskell改名要求キター

761 :デフォルト名無しさん :2007/02/15(木) 23:02:08

>>755

data Set

= Empty

| Pair Set Set

| Union Set

| Infinity

| Replacement Fun Set

| Power Set

こんな感じ?

762 :デフォルト名無しさん :2007/02/15(木) 23:06:59

>>759

確かにHaskellって名前あんまり良くないかも。

763 :デフォルト名無しさん :2007/02/15(木) 23:09:07

>>760

"Haskell" 自体は「専門用語」ではないから桶。

あれは「固有名詞」であって、云わば商品名のようなもの。

どんな名前をつけようが関係ない。


764 :デフォルト名無しさん :2007/02/15(木) 23:12:46

>749 >758

そっか、HaskellMonad圏論Monadは別物だったのか…ちょっと驚き

765 :デフォルト名無しさん :2007/02/15(木) 23:12:48

で、結局 Kleisli って、どう読むの?

766 :デフォルト名無しさん :2007/02/15(木) 23:39:55

クライスリーだそうです。

767 :デフォルト名無しさん :2007/02/15(木) 23:40:59

>>742

泥ス!! 定義5までは理解した気がするぉ!(^ω^)v 


(T μ η) が (対象 演算子 単位元)か。 しかし対象 T は T 1個だけか?

実は理解してないか?(^ω^;)?


定義6についてはこれからエロ画像見ながら考えるぉ

768 :デフォルト名無しさん :2007/02/15(木) 23:44:10

Tは自己函手だ。

μ、ηは自然変換。

769 :デフォルト名無しさん :2007/02/16(金) 00:28:35

>(T μ η) が (対象 演算子 単位元)か。

モノイドとしてみた場合の話だぉ。


770 :デフォルト名無しさん :2007/02/16(金) 01:03:24

>モノイドとしてみた場合の話だぉ。

モノイドとしてみるならTは集合としてみるべき。

771 :デフォルト名無しさん :2007/02/16(金) 01:46:57

>>756

すごく大雑把に言うと,チューリングマシン

λ計算などがあったところに,新しい定式化として

圏論に基づくものが現れたという背景がある.

現在,普通のプログラマチューリングマシン

λ計算を知らなくても特に問題は起きないけれど,

それと同じようなものだと考えるのが順当だと思う.

(もちろん知ってたほうが良いのは確かだけど,

 とりあえず大雑把なところを抑えておけば十分.)

ラーニングコストが高いのは,まだ新しい理論である

ということと,従来の手法よりも数学的に取り扱いやすい

枠組みとして導入されたことがあるので,教育用に

整理されてない現段階では,好きな人がやるものだと

思ったほうがよいと,個人的には思う.

772 :デフォルト名無しさん :2007/02/16(金) 01:56:04

>>764

別物というとちょっと語弊があって,

Kleisli triple と monad は一対一対応するので,

どちらで定義しても「本質的には同じもの」になる.

言い方としては,

 Haskellでは monad は Kleisli tripleで定義される

というのが間違いないと思う.

773 :デフォルト名無しさん :2007/02/16(金) 02:06:17

>>771

まだまだ未開拓なのか・・・。

>>772

>Kleisli triple と monad は一対一対応するので,

>どちらで定義しても「本質的には同じもの」になる.

!!ですよね。

774 :デフォルト名無しさん :2007/02/16(金) 02:45:29

     ...| ̄ ̄ | < この話はいつ終わるのかね?

   /:::|  ___|       ∧∧    ∧∧

  /::::_|___|_    ( 。_。).  ( 。_。)

  ||:::::::( ・∀・)     /<▽>  /<▽>

  ||::/ <ヽ∞/>\   |::::::;;;;::/  |::::::;;;;::/

  ||::|   <ヽ/>.- |  |:と),__」   |:と),__」

_..||::|   o  o ...|_ξ|:::::::::|    .|::::::::|

\  \__(久)__/_\::::::|    |:::::::|

.||.i\        、__ノフ \|    |:::::::|

.||ヽ .i\ _ __ ____ __ _.\   |::::::|

.|| ゙ヽ i    ハ i ハ i ハ i ハ |  し'_つ

.||   ゙|i〜^~^〜^~^〜^~^〜

775 :デフォルト名無しさん :2007/02/16(金) 02:52:32

ほかの面白そうな話が始まったら

776 :デフォルト名無しさん :2007/02/16(金) 03:09:00

main = この話 >> main

777 :デフォルト名無しさん :2007/02/16(金) 04:22:40

いや、この路線でいこう。

おれは、参加できないが。

778 :デフォルト名無しさん :2007/02/16(金) 11:52:48

結局、実際に有用なのはモナドのどの性質なんだ?

射の合成則なのか? 

対象に順番に射が作用しているという点で、結合則を利用しているようには見えないんだが?

ちんぷんかんぷんだぜ

779 :デフォルト名無しさん :2007/02/16(金) 13:40:19

python経由でならc++もよべるんですよね?

780 :デフォルト名無しさん :2007/02/16(金) 15:02:44

ごめん,だいぶ長文になった.うざかったらスルーしてくれ.

>>778

「射の合成則」は monad ではなく圏の性質なので

これを落とすと圏論で議論ができなくてうれしくない.

Monad を Kleisli triple (T,η,*) で定義したとき,

どれが利いているのかと言うと「全部そろって意味がある」

という答えになってしまう.

では,どんな意味があるのかというと,標語的に言えば,

monad は『計算』をモデル化できる構造」

となる.これはもう少し説明すると η, * が実際にどう働くかが

見やすくなるので,せっかくだから Haskell の計算をモデル化してみる.

781 :デフォルト名無しさん :2007/02/16(金) 15:09:47

続き.本当は以下の例は正しい Haskell の計算モデルでないし

定義もいくらか怪しいけれど,イメージということで許していただきたく.

>>778

例として

 sqr x = x * x,dup x = 2 * x

という関数を考え,sqr (dup 3) という『計算』を考えてみる.

いわゆる手続き言語ではこの式は

 sqr (dup 3) = sqr 6 = 36

と『計算』を次々と『値』に潰していくので

型は常に整合しているんだけど,Haskell では

 sqr (dup 3) = (dup 3) * (dup 3) = ...

『計算』そのものを『計算』していく.これは sqr の型を

考えるとちょっと奇妙.だけど monad (T,η,*) を

 T:X を「X を返す『計算」にうつす函手

 η:『値』をその値を取り続ける『計算』にする自然変換

 *:『値』を取る『計算』から『計算』をとる『計算』への変換

と定義してやり,sqr (dup 3) が本当は

 sqr* (dup* (η3))

を意味していると思うと,きれいに理解できる.

(この η, * は Kleisli triple の条件を満たしている.

 ほかの計算モデルでも η, * は同じような役割を果たすので

 Kleisli triple の条件が必要なのが理解できる)

782 :デフォルト名無しさん :2007/02/16(金) 20:16:29

>781

おお、何だか凄そうな人が!

いくつか質問させてください。

(1)

> T:X を「X を返す『計算」にうつす函手

> η:『値』をその値を取り続ける『計算』にする自然変換

> *:『値』を取る『計算』から『計算』をとる『計算』への変換

という定義から、

> この η, * は Kleisli triple の条件を満たしている.

は必ず言えるのでしょうか? 上の定義は型に関してKleisli tripleの条件を満たす+ηが自然変換

ということだと思うのですが、「ηが自然変換」ということからKleisli tripleの3条件が出てくるのでしょうか?

(2)

Kleisli tripleの3つめの条件

g* o f* = (g* o f)*

の直感的な意味はなんでしょう?

(3)

λ計算はCCCで普通に解釈できるのにsqr x = x * x,dup x = 2 * xになると

Kleisli categoryが必要になるのは、名前があるからでしょうか?

783 :デフォルト名無しさん :2007/02/17(土) 01:44:14

>>780-781

Haskellの旦那!ありがとう、かなり理解がすすんだぉ(Vipperなりに)。

>>733の定義6でKleisliトリプレットがモナドを為す事も、そこからKleisliカテゴリをだす事も

示せた(と思う ^ω^;)。


T μ (T μ T) = T μ (T*・T) = T*・(T*・T)

(T μ T)μ T  = (T*・T)μ T  = (T*・T)*・T

こんな感じで射だけを先に色々合成できるので、遅延評価を記述するのに便利

という風に納得したぉw

sqr* (dup* (η3)) = (sqr* ・ dup)* ・ (η3)

こんな風に使える?みたいな?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/norisuke3/20070216/1171645587
Connection: close