#数楽 Haskellにおける自由モナドとノイマン級数の話まず、ノイマン級数。ノイマン級数と言うと難しい話だと誤解する人が出るのでよろしくないのですが、みんなそう呼んでいるようなのでそう呼ぶことにする。ノイマン級数とは次の等比級数のことです。1+a+a^2+a^3+…

#数楽 続き。ノイマン級数1+a+a^2+a^3+…は数学のあちこちによく出て来ます。高校では|a|<1ならば1+a+a^2+…=1/(1-a)となることを習う。大学の線形代数では正方行列の級数E+A+A^2+…が収束するならば収束先は逆行列(E-A)^{-1}になることを知る。

#数楽 続き。行列Xが単位行列に何らかの意味で十分に近ければ、A=E-Xとおくと、E+A+A^2+…が(E-A)^{-1}=X^{-1}に収束し、単位行列に近い行列Xの逆行列の一つの計算の仕方が得られるわけです。行列の話は作用素の話に一般化される。続く

#数楽 続き。適切な線形代数の授業を受けていれば、行列の成分は実数や複素数のようなタイプの数ではなく、デジタルコンピューター的に0と1だけであってもよいことを知っているはず。ただし、1+1=0と約束しておく。有限体上の線形代数は役に立つ数学の典型例の一つです。続く

#数楽 リンクメモメルセンヌツイスター 有限体 行列 を検索https://www.google.co.jp/search?q=�%83�ルセンヌツイスター+有限体+行列 …擬似乱数発生法のメルセンヌツイスターは1+1=0の線形代数の典型的な応用例であることは有名だと思う。

#数楽 1+1=0と約束して有限体上の話にせずに、1+1=1と約束しても役に立つ数学を展開できる。すなわち足し算をOR演算とみなしても面白いことをできる。{0,1}における通常の掛け算はAND演算そのもの。足し算をOR演算とみなしても行列の積と和の計算の仕組みはうまく働く。続く

#数楽 続き。集合Xの部分集合Aは0と1のみを成分に持つサイズが"X"のベクトルと同一視できる。すなわち、x∈Xについて、x∈Aならばx番目の成分は1で、そうでないならばx番目の成分は0であるようなベクトルはXの部分集合Aと同じ情報量を持っている。続く

#数楽 続き。X={1,2,…,n}ならば普通のn次元ベクトルになる。同様にX×Yの部分集合Rはサイズ"X×Y"の行列と同一視できる。第(x,y)成分が1か0であるかを(x,y)がRに含まれるか否かで決めることによってサイズ"X×Y"の行列が得られる。続く

#数楽 続き。写像f:X→YからY×Xの部分集合{(f(x),x)|x∈X}が定まり、それから定まる行列をFと書こう。そのとき、行列Fとサイズ"X"のベクトルaの積Faはちょうど写像fでaに対応するXの部分集合Aをうつして得られるYの部分集合に対応している。続く。

#数楽 続き。このようにして集合間の任意の写像は0と1だけを成分にもつ行列(一般に無限サイズになる)の特別な場合だとみなされる。こういう言い方をすると非自明だと誤解してしまいそうだが、以上の話は自明でつまらない話の典型例の一つでしかない。単なる言い直し。続く

#数楽 続き。X×Xの部分集合R(このようなRはXにおける二項関係と呼ばれている)に対応する0と1だけを成分に持つ行列もRと書き、A=R+R^Tとおく(R^Tは転置行列)。このときノイマン級数E+A+A^2+…(和はOR演算)はRを含む最小の同値関係になっている。続く

#数楽 続き。RからA=R+R^T(ここでR^Tは転置で+はOR演算)を作る操作で対称律(対称行列性)が保証され、ノイマン級数の単位行列Eの部分から反射律が保証され、級数の無限和によって推移率が保証される。ノイマン級数は推移律を保証するための最小の手続きになっている。続く

#数楽 続き。数学では一般に「○○を含む最小の△△」のことを「○○で生成される(された)△△」と呼ぶ習慣になっている。その習慣を使えば「A=R+R^Tとおくとき、E+A+A^2+…はRから生成された同値関係になっている」と言うことができる。続く

#数楽 続き。Haskellにおける「自由モナド」の実装もノイマン級数の方法によっているとみなすこともできる。Fのノイマン級数を一時的にF^*=1+F+F^2+…と書こう(後で別の定義に移る)。このとき1+FF^*=1+F(1+F+F^2+…)=1+F+F^2+…=F^*. 続く

#数楽 続き。すなわち、Fのノイマン級数F^*はGを1+FGにうつす操作の不動点になっている。一つ前のツイートではFの左からの積と無限和を取る操作が可換であることを使ったが、そういうことを使わなくても、F_0=1, F_{n+1}=1+FF_nと定義して、～続く

#数楽 続き～、F(A+B)=FA+FBを使わなくても、F_0=1F_1=1+FF_2=1+F(1+F)F_3=1+F(1+F(1+F))F_4=1+F(1+F(1+F(1+F)))……の極限F^*が適切な意味で存在すれば、F^*=1+FF^*を満たすはず。続く

#数楽 続き。Haskellでの自由モナドの実装の仕方はまさに、以上のような考え方で函手FからHaskellの意味での自由モナドF^*=Free Fを作るようになっています。続く

#数楽 続き。足し算は交わりの無い和集合(非連結和)と解釈すると、F^*=1+FF^*はF^*(X) = X⊔F(F^*(X))を意味します。Haskellっぽい書き方ではFree F X = Pure X | Free (F (Free F X))となる。続く

#数楽 辞書集合と写像 ⇆ Haskell集合 ⇄ 型写像 ⇄ 函数直積 × ⇄ ( , )直和 ⊔ ⇄ |F^*(X)=X⊔F(F^*(X)) ⇄ Free F X = Pure X | Free (F (Free F X))

#数楽 例えば、F(X)={(op x x')|x,y∈X}のときF_0(X)={x}F_1(X)={x, (op x x')}F_2(X)={x, (op x x'), (op (op x x') x''), (op x (op x' x''))}…続く～

#数楽 続き。以上のT=F^*は函手F(X)={(op x x')|x,x'∈X}から生成される自由モナドになっています。このようなモナドもモナドの典型例です。そしてT代数は二項演算が定められた集合と同じものになります。T(X)は自由T代数になる。続く

#数楽 続き。自由モナドは二項演算がopの一つだけではなく、k項演算(k=0,1,2,…)を複数個の場合にも同様に作れます。そのような自由モナドをTと書くと、T(X)は集合Xの元達に複数の演算記号を形式的に有限回施した結果全体の集合になります。続く

#数楽 続き。そのときT代数は複数の演算が定義されている集合と一致する。この例を知っていれば、自由モナドとT代数の典型的な例が多数得られ、どうしてT代数という言い方でモナドが代数を定めるかのように言いたくなる理由もわかります。

#数楽 もしかしたら、モナドの典型例として以上のタイプの自由モナドの例を最初から説明した方がわかりやすかったかも。どうしてT代数を考えたくなるかも、演算子を含む形式的な式全体を作る操作が自由モナドになることを知っていればわかると思う。続く

#数楽 一般に函手Fに対してF代数が「函数α:F(X)→Xが与えられたX」と定義されます。F(X)={(op x x')|x,x'∈X}ならば函数αは式(op x x')を評価して値を得る函数になります。これは二項演算opを持つ代数の一種です。より複雑な式は自由モナドで扱える。

#数楽 これでHaskellにおいて有名なモナドの例については大体説明が終わったことにしていいと思う。(何か忘れている易しい重要な例は残っているか？)

#数楽 高校で数学を習えば等比数列の和(ノイマン級数) a^*=1+a+a^2+a^3+…=がa^*=1+aa^*を満たしていることを理解できる。同様に F^*=1+FF^* によってFから生成される自由モナドF^*も得られる。やはり柔らかい頭で数学を勉強しておくことは大事。

#数楽 続き。a=1/3についてa^*=1+a+a^2+…を計算するとa^*=3/2となることがわかる。数の計算なのでa^*を理解することは易しい。それに対して、函手Fに対する1+F(1+F(…Ｆ(1+F)…))のネストを増やす極限F^*の理解はややこしい。続く

#数楽 続き。似たような話は代数学入門として群論を勉強する場合にもよく出て来ます。有限群の元の個数は自然数になり、算数でたくさんの計算を練習したのですが、有限群に関する計算はずっとややこしくなり、簡単に理解することは難しくなります。続く

#数楽 続き。しかし、「数でできていたような計算を函手や群でもできないだろうか？」と考えることはとても有益です。その手の曖昧な問題を考えるときには論理的に正確な推論能力がものすごく役に立ちます。論理的スキルがあればいい加減で曖昧なことを考えてもバランスを崩さずにすむ。

#数楽 続き。将棋や囲碁の強い人達はまるで直観的に考えて結論を出しているように見えても裏では正確な「読み」の力が自動的に起動しているのと同じように、数学に関わるあらゆる事柄でも直観と論理が同時に働くような頭の使い方をすることは重要だと思います。

#数楽 リンクメモ【Haskell】48時間でSchemeを書こうhttps://ja.m.wikibooks.org/wiki/48�%82間でSchemeを書こう …

#数楽 リンクメモ【Haskell】Haskell で作る micro Schemehttp://www.geocities.jp/m_hiroi/func/haskell33.html …

#数楽 ノイマン級数1+a+a^2+…に関する話を追加。「Haskellでは函手Fから生成されるモナドをノイマン級数 1+F(1+F(1+F(…)))によって実装しているとみなせる」という話をしたのでした。集合Xから生成されるモノイドは 1+X+X^2+X^3+…ですね。

#数楽 T=1+F(1+F(1+F(…)))とおくとT=1+FT、すなわちTX=X+FTX。Haskell的記号法ではTX=Free f xであり、Free f x = Pure x | Free (f (Free f x))Pureと|の直後のFreeは単なる識別子。続く

#数楽 TX=X+FTXに函手構造は、函数φ:X→Yに対して函数Tφ:TX→TYを「x∈TX=X+FTXについて、x∈XのときTφ(x)=φ(x)∈Y、x∈FTXのとき帰納的にTφ(x)=FTφ(x)∈FTY」(注意：FTφ:FTX→FTY)と定めることによって構成されます。

#数楽 続き。T=1+F(1+F(1+F(…)))の「…」の部分の意味を曖昧なままにしておいたのですが、その部分の意味が帰納的な定義を可能にする類のものであれば一つ前のツイートの内容はうまく行きます。続く

#数楽 続き。TX=X+FTXのモナド構造の定義は「函数f:X→TYに対して函数φ^*:TX→TYを、x∈TX=X+FTXについて、x∈Xのときφ^*(x)=φ(x)∈Y、x∈FTXのとき帰納的にφ^*(x)=Fφ^*(x)∈FTYと定める」(注意：Fφ^*:FTX→FTY)。

#数楽 「x∈Xのときφ^*(x)=φ(x)∈Y、x∈FTXのとき帰納的にφ^*(x)=Fφ^*(x)∈FTY」と定義されたφ^*はHaskell的記号法では(>>= φ)となり、φ^*(x)はx>>=φとなります。続く

#数楽 続き。さらにφ^*の定義はHaskell的には(Pure x) >>= φ = φ x ← x∈Xのときφ^*(x)=φ(x)(Free x) >>= φ = Free (fmap (>>= φ) x) ←x∈FTXのとき帰納的にφ^*(x)=Fφ^*(x)

#数楽 続き。数学は知っているが、Haskellを知らない人は「>>=」という記号法のせいで理解できなくなる可能性がある。モナドTと函数φ:X→TYに対して、モナド構造から定まる函数φ^*:TX→TYを(>>= φ)と書き、その値φ^*(x)をx>>=φと書きます。

#数楽 「函数型プログラミングって函数達をうまく合成して欲しいプログラムを作る話なんでしょ？」という思い込みのもとでHaskellの入門書を見ると、いきなり函数達の合成には見えない書き方(do式)で書かれていて「いきなりわからなくなる」ということがあるかもしれません(笑)。続く

#数楽 続き。一般に、モナドTに対して、自由T代数TX達の圏が得られ、自由T代数の圏における射φ^*:TX→TYは函数φ:X→TYと一対一に対応しています。函数φ:X→TYと函数ψ:Y→TZは直接的には合成できないのですが、自由T代数の圏における射としては合成できる。続く

#数楽 自由T代数の圏における射の合成をそう見えないように書くための構文糖衣がHaskellにおけるdo式です。函数φ:X→TYと函数ψ:Y→TZを自由T代数の圏における射とみなして合成したものをx∈TXに作用させた結果ψ^*(φ^*(x))はx>>=φ>>=ψと書かれます。続く

#数楽 続き。函数を定義したり、何かを代入するときに、同じものを何度も繰り返し使う場合があります。さらに直接代入するのではなく、一時的に別名を付けてから代入した方が読み易い場合も多い。これは普通に数学的議論を紙の上でやる場合にもプログラミングでも同じことです。続く

#数楽 続き。そのためにHaskellで容易されているのはletとwhereです。別名を使った後に定義するためにはwhereを使います。紙の上で数学を行う場合にも「なにはともあれ式を書き切ってから、そこで使われた未定義の記号をwhereと書いて説明すること」はよくあります。

#数楽 do式はモナド上の自由代数圏における射の合成をまるで命令の逐次実行のように書くための記号法です。途中でletやwhereなども自由に使える。途中でX→1→TY型の射を経由するとそれ以前の計算結果はすべて廃棄され次の計算が実行されることになります(Haskellでの>>)。

#数楽 続き。こういう仕組みなので、「Haskell入門」でいきなりdo式を見せられたときに「なんとなく」ではなく「クリアに」何をやっているかを理解しようとすると、結局のところモナドの周辺について理解する必要が生じてしまうわけです。「なんとなく」で先に進めない人はつらそう。

#数楽 続き。「自由〇〇代数」に関する数学について素養があれば、自由T代数間の射φ^*:TX→TYと写像φ:X→TYが一対一に対応していることは「自由〇〇代数」の定義および直観から直接的に出て来るので、どういう写像(函数)の合成を考えているかどうかはすぐにわかる。続く

#数楽 続き。しかし、自由T代数間の射(準同型写像)の合成によってどのようにプログラミングできるかは非自明で面白い話だと思いました。以上がしろうとによる率直な感想。

#数楽 続き。実際には「\x -> func1 x」で切れるわけではないので、括弧を入れた方がわかりやすいかも。\x -> (func1(x)>>=(\y -> (thing2>>=(\_ -> (func2(y)>>=(\z -> return(z))))))続く

#数楽 func1:X→TY、func2:Y→TZとする。>>=(\z -> return(z))は単位射η_Z:Z→TZに対応する恒等射TZ→TZです。func2(y)>>=(\z -> return(z))はfunc2(y)∈TZの単位射で移った先func2(y)です。

#数楽 (\_->(func2(y)>>=(\z -> return(z))))は任意の_∈Y'をfunc2(y)∈TZに対応させる函数。(thing2>>=(\_->(func2(y)>>=(\z->return(z)))))はその函数に対応する自由T代数の射で～続く

#数楽 続き～thing2∈TYを移した先です(それをφ(y)∈TZと書く)。(\y->(thing2>>=(\_->(func2(y)>>=(\z -> return(z)))))はy∈Yをφ(y)∈TZに移す函数φ:Y→TZ。対応する自由T代数の射をφ^*と書く。続く

#数楽 続き\x->(func1(x)>>=(\y->(thing2>>=(\_->(func2(y)>>=(\z->return(z))))))はx∈Xをφ^*(func1(x))に対応させる函数です。それをψと書き、対応する自由T代数の射をψ^*:TX→TZと書く。続く

#数楽 続きthing1>>=(\x->(func1(x)>>=(\y->(thing2>>=(\_->(func2(y)>>=(\z->return(z)))))))はψ^*(thing1)∈TZです。もしかしたらどこかでケアレスミスしているかもしれませんが、こんな感じ。

#数楽 再訂正版。以上で仮に採用した設定ではTはモナドでthing1∈TXfunc1:X→TYthing2∈TY'(_↦thing2):Y→TY'func2:Y→TZreturn:Z→TZこれらを(下から)順番に「合成」する話。

#数楽 訂正版。対応する自由T代数の射>>=func1:X→TY>>=(_↦thing2):TY→TY'>>=func2:TY→TZ>>=return:TZ→TZ

#数楽 モナドTでは、函数φ:X→TXとα∈TXに関するα>>=φやα>>=(x↦φ(x))のような記号法で、Xの元しか代入できないはずのφ(x)のxにTXの元αを代入できます。これはTXがXから生成してれる自由代数の一種であり、自由代数の概念を理解していれば当然という感じ。続く

#数楽 集合Xから生成される自由代数とは「Xの元達から生成される何かで各x∈Xに自由に何でも代入できるものたち」のことです。代入は算数で3×△の△に4を代入して12という数を得るときにすでに習ってしまっています。モナド上の自由代数版の話はそういう話の大幅な一般化になっています。

#数楽 例えば文字集合X={a,b,…}から中学生数学で多項式を作る方法を教わります。集合Xから生成される(Z上の)多項式全体の集合をTXと書くと、Tはモナドになります。そしてT代数は可換環と一致し、多項式環TX達が自由T代数達になります。続く

#数楽 続き。そして、別の文字集合Y={α,β,…}を用意して、元の文字集合Xから文字集合Yから作った多項式全体の集合TYへの函数φを考えましょう。φはXに含まれる文字a,b,…の各々をそれぞれα,β,…の多項式φ(a),φ(b),…に対応させます。続く

#数楽 続き。文字a,b,…のそれぞれにφ(a),φ(b),…を代入する操作f(a,b,…)↦f(φ(a),φ(b),…)は多項式を多項式に移す函数φ^*:TX→TYを定めます。この例を知っていればモナドの話と中学校数学がもろに繋がります。続く

#数楽 たとえば、x^2+2x+yにx=ξ-1,y=α+1を代入して(ξ-1)^2+2(ξ-1)+α+1=ξ^2-αを得るというような計算は(x^2+2x+y)>>=(x↦ξ-1,y↦α+1)を計算していることになっているのです。>>=は代入の操作になっている！

#数楽 代数を「多項式環」よりももっと簡単な「自由モノイド」=「リスト」にしても代入の操作は可能です。[x,y,z]>>=(x↦[2,7,1],y↦[],z↦=[8])は[2,7,1,8]になります。こういうことができるのでリストはモナドになる。続く

#数楽 リスト(自由モノイド)よりもさらに簡単な代数を考えることもできます。集合Xにおまけの要素Nothingを付け加えたものをTX=X⊔{Nothing}と書くと、Nothingは常にNothingに移るという規則(代数のルール)でTは自然にモナドなります。Maybeモナド。

#数楽 続き。X={1,2}でY={hoge}のとき、函数φ:X→TYを1↦hoge,2↦Nothingと定めると、1>>=φはhogeになり、2>>=φとNothing>>=φはNothingになります。これも単純な代入の操作です。この例は簡単過ぎてピンと来ない例かも。

#数楽 ちなみに、Maybeモナドは全ての集合Xを一点集合に{Nothing}に移す函手から生成された自由モナドにもなっています。

#数楽 Maybeモナドはエラーの処理に使えます。例えば次のリンク先の第2節を見てください。http://www.randomhacks.net/2007/03/10/haskell-8-ways-to-report-errors/ …8 ways to report errors in Haskell

#数楽 TをTX=R^R^X=((X→R)→R)={XからRへの函数にRの要素を対応させる函数全体}と定めても、Tは自然にモナドになります。これは継続渡しスタイル(cps)で使われるモナドなので、継続モナドと呼ばれています。

#数楽 続き。函数φ:X→TY=R^R^Yが与えられたとき、f∈TX=R^R^Xに対して、(f>>=φ)∈TY=R^R^Yがg:Y→Rをf(x↦φ(x)(g))∈Rに対応させる函数として自然に定まります。fの中のxにφ(x)を代入する操作っぽいことをできている。だからTはモナド。

#数楽 継続モナドのcallCC函数を使っても例外的なことが生じたときに処理を中断して処理をすることができます。https://twitter.com/genkuroki/status/832239973101211649 …

#数楽 TをTX=(X×S)^Sと定め直す。φ:X→TYとf∈TX、f(s')=(x(s'),s(s'))に対してTYの元が(f>>=φ)=(s'↦φ(x(s'))(s(s')))と定まり、Tはモナドになる(状態モナド)。これはfの中のxをφで移す操作になっている。

#数楽 続き。やはりxをφ(x)に置き換える操作(代入の操作)に見える。モナドTと函数φ:X→TYが与えられると、f∈TXの中のxをφ(x)で置き換えることによって(f>>=φ)=φ^*(f)∈TYが得られます。まさに自由代数の話。

#数楽 というわけで、Haskellにおける「f>>=(\x->ほげほげ)」すなわちdo x<-f 「ほげほげ」の部分の翻訳は「xをほげほげに置き換える操作をfに施した結果」を表すと解釈できます。

#数楽 モナドTにおいて、函数φ:X→TYはTXの要素fの中のXの要素をTYの要素で置き換える方法を指定しているとみなせ、f>>=φはfの中のXの要素をφで置き換えた結果を表します。こういう置き換えの操作ができることはほとんどモナドの定義そのものと思っても構いません。