リストモナドと沢山のbind

また蟻本を読んでた。部分和問題という「数のリストと、目指す数が与えられて、数のリストから数を0個か1個ずつ選んで、その総和を目指す数にできるか？」という問題を解いていて、「あ！これって先のくじびきと同じ問題だ！」となったのであった。

くじびきは「数がいくらか与えられて、その数たちを重複を許して4つ選んで、その総和を目指す数にできるか？」という問題で、素朴にはこんな感じになる。

で、書こうと思ったのだが、くじびきなら「4つ」って決まっていたが、今回はいくつ数字が飛んでくるか分からない。「a <- [0, 1]」で、「1を取るか取らないか」という不定性を表現するつもりだったのに書けないじゃないかと思った。が、よく考えたら「リストのなかのモナド値をモナド値としてのリストにする」という関数があったなと思って、調べたらsequenceだった。というわけで、そのコードがこちら。

これで、数のリストが[1, 2, 3]とあったらそれを[[0,1],[0,2],[0,3]]と、取るか取らないかの不定性をそれぞれ持たせて、sequenceでうまくbindできた。

たしかに色んな本にaにsequenceを使う例はあったんだけど、こういう意味があるということに気付いてうれしい。

Functorとしての関数とFunctorとしてのリスト

Haskell

最近すごいH本を読み直していて、11章のFunctorとしての関数の話で気付きがあって、一度忘れてまた思い出したので今度はちゃんと書き留めておく。大した話ではない。

Haskellのリストは、そういう需要が分かりやすく存在するからなのか分かりやすいFunctorで、

fmap (*2) [1,2,3]

と書いたらこれはちゃんと

[2,4,6]

となってくれる。リストの各々に大して関数を適用したいという場面はある程度プログラミングをしていれば無限に遭遇する場面だと思う。

ただ、関数もFunctorであって、

fmap (+1) (*2)

は

(*2).(+1)

と同じになるというのは若干分かりづらい。関数がFunctorであるというのをもうちょっと調べると、型aにFunctor*1(b->a)とできるということになる。ちょっと実験してみると、

(return :: (a -> (b -> a))) 1 2

は1になるし、

(return :: (a -> (b -> a))) 1 3

も1になるし、

(return :: (a -> (b -> a))) 1 4

も1になる。returnってそういうものだった。

さて、型aを包んで(b -> a)にしてくれる関数のFunctor(b -> )が分かりづらいという話だった。しかし一方、型aを包んで[a]にしてくれるリストはFunctorとしてわかりやすい。しかし、よくよく考えてみると、高校でひょっとしたら学ぶようにリスト[a]、あるいはa型の数列は結局のところ自然数から型aへの写像であった。例えば、初項1、公差2の数列

1,3,5,7,...

は、関数

(\n -> 2*n - 1)

と同一視できる。数列のn番目を求めたければ、この関数にnを入れれば確かにうまく行く。
そう考えると、型aを包んで[a]にするというのは、型aを包んで(Int -> a)にするということになる。例えば、fmapを使って数列を1増やすというのを考える。

fmap (+1) [1,3,5,7..]

は、

[2,4,6,8..]

になる。一方、

fmap (+1) (\n -> 2*n -1)

を考えると、ここに1,2,3,...を入れてできた数列はさっきの

[2,4,6,8..]

に一致する。

まとめると、Functor(b ->)が型aを包んで(b -> a)にするのは、bをIntと見ると、Functor[]が型aを包んで[a]にするのとちゃんと似ているなあというお話でした。

*1:->) b)、あるいは(b ->)で包んで((ウルトラどうでもいいが「くるむ」と読みたい

今日の英語

"I'm tired from the extra exam."

追試で疲れたと言おうとして "tired for" と言って直してもらった。あと、"extra exam"で追試というのは通じなかった。

"relationship of the position to the temperature"

Fourier解析の話をしようとして"relation of the position with the temperature"と言った。今調べたら"of - to"なのね。

shellac, varnish, wax

resin

松脂のことだったらしい。

inorganic

無機化学の無機ってこれなのね。

ルベーグ積分をあえて使ってみる

(2018年8月31日追記)別にこのぐらいの積分順序の交換ならルベーグ積分でもできる気がするので「ルベーグ積分を使う」というタイトルは不適切かもです。


たまたまルベーグ積分の追試にむけて勉強しているときに、

というツイートを見掛けて、ルベーグ積分便利に使えたりするかなあと思って試してみた。
本当は1/nごとに区切って部分積分してx^2を消していったりするのだろうけど検算はしなかった。被積分関数が\pi^2で抑えられ、積分区間も有界なのでnと無関係な可積分関数で抑えられて、優収束定理が適用できることに注意する。

\begin{align} \lim_{n\to\infty}\int_0^\pi x^2|{\sin nx}|dx &= \lim_{n\to\infty}\int_0^\pi \left(\int_0^x 2y dy\right)|{\sin nx}|dx \\ &= \lim_{n\to\infty} \int_0^\pi \int_y^\pi 2y |{\sin nx}|dxdy\\ & \text{(非負関数へのフビニの定理で積分順序を交換)}\\ &= \lim_{n\to\infty} \int_0^\pi 2y \left(\int_y^\pi|{\sin nx}|dx\right)dy \end{align}
上のフビニの定理の適用のところは、こういう積分範囲をイメージする。
f:id:sle:20141206124039p:plain


各nに対して\frac{i}{n}\pi\le y \le \frac{i+1}{n}\piとなるi(0\le i < n)がただ1つ存在する。これについて、
\frac{n-i-1}{n}=\int_{(i+1)\pi/n}^\pi|{\sin nx}|dx \le \int_y^\pi|{\sin nx}|dx \le \int_{i\pi/n}^\pi|{\sin nx}|dx= \frac{n-i}{n}
が成立する。i/n \to y/\pi(n\to\infty)に注意して、
\lim_{n\to\infty} \int_y^\pi|{\sin nx}|dx = 1-y/\pi
を得る。さっきの計算のつづきで、

\begin{align} \lim_{n\to\infty} \int_0^\pi 2y \left(\int_y^\pi|{\sin nx}|dx\right)dy &= \int_0^\pi 2y \lim_{n\to\infty} \left(\int_y^\pi|{\sin nx}|dx\right)dy\\ &\text{(優収束定理で極限と積分を交換)}\\ &= \int_0^\pi 2y(1-y/\pi)dy\\ &= \pi^2-\frac{2}{3\pi}\pi^3\\ &= \frac{\pi^2}{3}. \end{align}
高校数学の範囲なら積分の順序変更とか積分と極限の交換は好きにやっていいんじゃないかなあという気もする。

あと、追試が近いので定理の適用の誤解とかあったら教えてください。

追記:

ということなので修正してました。追試駄目なのでは。

確かにあの\sin nxの積分が間違ってて、
\int_0^{\pi/2} \sin xdx = \cos 0 - \cos \pi/2 = 1- 0 = 1
であって、上の計算では
\int_0^{\pi} \sin xdx = 1
と誤った記憶をもとに計算してしまっていた。山半分の広さが1で、山1つの広さは2です。
したがって、正しくは、
2\frac{n-i-1}{n}=\int_{(i+1)\pi/n}^\pi|{\sin nx}|dx \le \int_y^\pi|{\sin nx}|dx \le \int_{i\pi/n}^\pi|{\sin nx}|dx= 2\frac{n-i}{n}
であって、
\lim_{n\to\infty} \int_y^\pi|{\sin nx}|dx = 2(1-y/\pi)
となって、
\begin{align} \lim_{n\to\infty} \int_0^\pi 2y \left(\int_y^\pi|{\sin nx}|dx\right)dy &= \int_0^\pi 2y \lim_{n\to\infty} \left(\int_y^\pi|{\sin nx}|dx\right)dy\\ &\text{(優収束定理で極限と積分を交換)}\\ &= \int_0^\pi 2y(2(1-y/\pi))dy\\ &= 2\left(\pi^2-\frac{2}{3\pi}\pi^3\right)\\ &= \frac{2}{3}\pi^2. \end{align}
となる。悲しい。

追記2:

とのご意見を頂いたので本文を修正しました。

ある点を無限回通る閉曲線

math


もうちょっと真面目に言うと、電車が混んでいてKindleぐらいしか使えなくて、たまたま入ってたHatcherを読んでいて「n>2のときS^n上の曲線は一点に縮まる」みたいなのが載っていて、その証明を読んでいて考えていた。

曲線は[0,1]でパラメタ付いていているとする。はじめは単位円を1/2秒かけて1周し、1/4秒かけて2周目を回り、1/8秒かけて3周目を回り…とすればよいかなあとか思ったけど、時刻1のところで連続性が失われてしまった。結局もうちょっと修正して、はじめは単位円を1/2秒かけて1周し、1/4秒かけて半径1/2の始点の一致する円を1周し、1/8秒かけて半径1/4の始点の一致する円を一周し…とすると時刻1に近づくにつれて点がどんどん縮んでいって連続性もOKだなあと思った。あとどうでもいいが、この曲線は長さが有限になる。

f:id:sle:20140215014034p:plain

ポストモダン解析学: [定義13.3]分割と回転(解決)

ポストモダン解析学 math

http://ashiato45.hatenablog.jp/entry/2013/09/24/201659で夏休みから悩んでた積分の値の極限の一致なのだけれど、ついにC85の三日目の店番中に解決を見た。夜だけど書いておく。

まじめな記述については、足跡45のサイト>ポストモダン解析学の「証明メモを見る」のところにpdfで置いてある。

なんとなくの概略を書いてみるが、ちゃらんぽらんではある。

イメージとしては、fの台を囲む正方形が2つあってその上で棒グラフでfの形を近似しているという状況で、その棒グラフの体積が2つとも大体一致するよね？という話だった。しかし、正方形の分割が互いに斜めになっているかもしれないので、結局その分割したものをあわせると変な三角形とかが出てきて、その「面積」はよく分からないのでそこから先に進めないというのが問題だった。そこで、なんとかその変な図形に対して「面積」を定義するのを回避して、正方形に対する「面積」だけで片付けようと考えていたのが多分C85の1-2日目ぐらい。ちなみに、正方形に「面積」があるのはポストモダン解析学の定義13.3の積分の定義で暗に\int f(x) dx = \sum c_i (l/n)^dと、(l/n)^dの形で表れている。

結局「面積」を具体的に値にするのは最後だけで済ませて、途中に他の多角形に対する「面積」を出すにしてもそれを抽象的なσ(多角形)という実数で済ませようと思った。必要なのは「多角形の『面積』を足すと、その多角形が集ってできている元の正方形の『面積』に一致する」ということなので、それさえ満たせばもはや「面積」は僕等の直感的な面積でなくてもよくて、果ては負の数でさえよいのではないか、ということを考えると多角形の「面積」の値をどう定めるかという問題は「多角形の『面積』を足すと、その多角形が集ってできている元の正方形の『面積』に一致する」を満たすという条件を記述した連立一次方程式が解を持つかという問題に帰着される。で、解を持つかどうかだが、多角形を出鱈目に切り刻んで係数行列のほうを好きなだけ横長にすることができるので、解を持つように無理矢理することができる。あとは直感通り計算するだけ。