読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

確率と測度

定義を忘れないようにまとめ。用語とかは以下の本のもの。はじめての確率論 測度から確率へ佐藤 坦 Ωを標本空間となる集合とする。これは任意の集合でよい。 σ-集合体 Ωの部分集合の集合B⊂P(Ω)がσ-集合体 ⇔ Ω∈B、a∈B⇒a^C∈B、A_k∈B⇒∪A_k∈B (加算無限和) σ集合…

今日は 圏論勉強会 第13回 の日です

元祖圏論勉強会ではない方の圏論勉強会 第13回の最終回です。資料とustreamは公開されています。 ワークスアプリケーションズさんに感謝 三脚復活してる! 第13回: 随伴・モナド / 講師 @9_ties さん 「モナドが途中で終わるのは嫌でしょう」「随伴を説明し…

今日は 圏論勉強会 第12回 の日です

木曜日なので圏論勉強会ではない方の圏論勉強会 第12回に来ています。資料とustreamは公開されています。 ワークスアプリケーションズさんに感謝 ついに三脚が貸してもらえなくなった 第12回: 自然性・米田の補題 / 講師 @9_ties さん 圏論は自然性の記述の…

今日は 圏論勉強会 第11回 の日です

毎度おなじみ、圏論勉強会ではない方の圏論勉強会 第11回に来ています。資料とustreamは公開されています。 ワークスアプリケーションズさんに感謝 第11回: 指数対象・デカルト閉圏 / 講師 @9_ties さん 今日からはがらっと話が変わるので、前回までの話は忘…

今日は 圏論勉強会 第10回 の日です

今週も圏論勉強会ではない方の圏論勉強会 第10回に来ています。資料とustreamは公開されています。 とびいりの話は大歓迎なので、面白い話がある人は面白くなくても言って下さい 13回目もやる(12回だとモナドに入れない。最終回はモナド) ワークスアプリケー…

今日は 圏論勉強会 第9回 の日です

前々回ぶりに圏論勉強会ではない方の圏論勉強会 第9回に来ています。資料とustreamは公開されています。 ワークスアプリケーションズさんに感謝 前回の練習問題の回答を作りますのでお楽しみに 第9回: 領域理論・不動点意味論 / 講師 @9_ties さん 意味論は…

今日は 圏論勉強会 第7回 の日です

圏論勉強会ではない方の圏論勉強会 第7回です。資料とustreamは公開されています。 司会の方がワークスアプリケーションズ社を退社されたので今回からバトンタッチ 後半第一回目 第7回: 様々な極限 | 代数的データ型 / 講師 @9_ties さん 1時間で話せる内容…

今日は 圏論勉強会 第6回 の日です

圏論勉強会ではない方の圏論勉強会 第6回です。資料とustreamは公開されています。 第6回: 積・余積・極限 / 講師 @9_ties さん 普遍性の概念によって定義される極限と余極限について 終対象 任意の対象から射がひとつだけ存在 同型を除いて一意 1と1'があれ…

今日は 圏論勉強会 第5回 の日です

圏論勉強会ではない方の圏論勉強会 第5回です。資料とustreamは公開されています。 今日は倚子が追加された ワークスアプリケーションズ社さんに感謝しましよう 第5回: 様々な射 / 講師 @9_ties さん Hom集合についての補足 A言語とB言語のトランスレーターt…

私のHom関手暗記法

圏論勉強会 第4回のHom関手で悲鳴が上がってたので補足してみる。Hom関手がなんであるかは@9_tiesさんもおっしゃっていたようにひたすら手を動かすしかなくて、圏論を覚えたいのであればしっかりと復習する必要がある部分なのは間違いない。とは言え、効率の…

今日は 圏論勉強会 第4回 の日です

圏論勉強会ではない方の圏論勉強会 第4回にまたやって来ました。資料とustreamは公開されています。 ワークスアプリケーションズ社に入ると、リハーサルも見れてお得だよ! 第4回: 射で考える / 講師 @9_ties さん 様々な概念を圏論の言葉のみで述べる 今日…

今日は 圏論勉強会 第3回 の日です

圏論勉強会ではない方の圏論勉強会 第3回に来ました。資料とustreamは公開されています。 今回からヘッドセット完備 中高生も見ているらしい(のでプログラミング以外のネタも) 第3回: 様々な圏 / 講師 @9_ties さん 視野が狭くならないよう、プログラムに関…

自由マグマを自由対象の定義の図で書くと

圏論勉強会 第3回の自由対象で悲鳴が上がってたようなので、参考までに図に書いて説明しておく。まず、マグマと自由マグマを以下のように定義する(というか、勉強会においてこう定義していた)。 class Magma a where magappend :: a -> a -> a data FreeMagm…

自由モノイドとFreeモナド

以前、モナドは自己関手圏におけるモノイドであるという話をしたことがあるのだけど、この時は理解が足りなくてFreeモナドにまで踏み込めなかった。今日調べていたら、Free Monoid Objectsというわかりやすいエントリを見つけたので簡単に紹介。まず、以前の…

今日は 圏論勉強会 第2回 の日です

圏論勉強会ではないモノイド勉・・・いや、圏論勉強会 第2回に来ました。資料とustreamは公開されています。 第2回: モノイド・群 / 講師 @9_ties さん モノイド、圏は計算機に必要な概念 対象が1つの圏。シンプルだけどシンプル過ぎない圏 約束: 自然数は0…

今日は 圏論勉強会 第1回 の日です

圏論勉強会ではない圏論勉強会 第1回に来ました。資料とustreamは公開されています。 @seizans さんより ekmett勉強会でekmettさんが圏論勉強するといいよというから開催 日本始まったな 講師 @9_ties さん 圏論だけではなく、圏論を題材に色んなことを学ぶ…

スツルムの定理の直感的な解説

昨日の計算機代数勉強会で代数的実数の実装のために出てきたスツルムの定理、共立出版の数値解析でも近似値の算出に使っており、証明も詳しく載っている。互除法だけではなく3重対角行列の主小行列式がスツルム列をなすことを使って固有値の算出をしたりもし…

今日は Haskellで計算機代数勉強会 の日です

せっかくのGWなので、朝からHaskellで計算機代数勉強会に来ています。内容が内容なので正確性は保証できませんが、自分用のメモということで。 HALでもわかるGröbner基底 / @mr_konn さん グレブナー基底 高次連立方程式、初等幾何、統計ロボティクス、計算…

今日は「データベースは圏なんだよ!の会」の日です

中原市民館に来ております。データベースは圏なんだそうです。SGL読書会の姉妹イベントです。 Databases are categories by Spivakさん / @bonotakeさん Spivakさんのスライドの解説です。 情報の世界の coherence の欠如を解決するためにフレームワークが必…

"圏論とかモナドなんて簡単だからscalaを使って説明してみた"を検証してみた

射っていうのはscalaだと単なる関数だし、関手はmap、モナドはflatMapなだけです。これのどこが難しいというのでしょう。圏論とかモナドなんて簡単だからscalaを使って説明してみた 内容について考えてみよう。 圏の定義? trait Cat { type A type B def f:…

MonoidもMonadもモノイドだって話

わかめのモナド浸しと第6回 スタートHaskell2で「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」という話をしてきた。スライドは以下。 モナモナ言うモナド入門 *1 モナモナ言うモナド入門.tar.gz .tar.gz の方はHaskellでの説明だ…

「プログラム意味論」が面白かった

ずーっと前から読みたかったけど絶版になってしまって読めなかった本が復刊。 プログラム意味論 (情報数学講座)横内 寛文 最初はラムダ計算とコンビネータ理論から入り、3章で領域理論について解説する。posetの取り扱いとか最小不動点定理とかまともに学ん…

PerlによるFreeモナドの実装

悟りを開けると話題のFreeモナドをPerlで実装した。実装はこちら。 Freeモナドとは? モナドの性質の1つとして、flatten : TTX → TX (または join、またはη)によって重複する関手Tを1つに押しつぶせるという点がある。そのお陰で、TTTTTTXのようにTが複数あ…

「フカシギの数え方」をPerlで解く

まずはこの動画を見るべし → 『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!。 きちんとした解答がすでに上がっている → 「フカシギの数え方」の問題を解いてみた。 まあでも、これだけ力作な動画を見せられたら自分でも解いてみたい…

「プログラミング言語の基礎概念」を読んだ

学部生向けなのでさくさく読めてよい。 プログラミング言語の基礎概念 (ライブラリ情報学コア・テキスト)五十嵐 淳 カバーしているのは操作的意味論*1で、序盤から中盤にかけて単純な自然数の和積算の意味論をベースに徐々に盛りつけてMLライクな言語の意味…

今日は社会ネットワーク分析勉強会 #1の日です

社会ネットワーク分析勉強会 #1にお邪魔しています。タグは#TokyoSNAです。Niftyさんのエンジニアサポートという制度で行われているようです。Nifty++

問題4.19の解答(台形公式、シンプソンの公式)

概説微分積分の問題4.19の解答。台形公式は定積分を台形で近似するもの。台形の公式を使って面積を出して整理すればすぐ出てくる。 def trapezoidal(f, range_, n): a, b = range_ result = f(a) + f(b) for i in xrange(1, n): result += f(a + (b - a) * i…

問題4.13の解答(回転体の表面積)

概説微分積分の問題4.13の解答。公式をそのまんま利用。 import sympy as sym from sympy.utilities import lambdify import scipy as sp import scipy.integrate def surface_of_revolution(y, range_): dy = sym.diff(y, x) y_lambda = lambdify(x, y) dy_…

問題4.7と4.8の解答(不定積分と定積分)

概説微分積分の問題4.7と4.8の解答。手計算に飽きたので現実逃避。4.7 は sympy を使う。理論的に解けるのはわかってるけども、手計算じゃもはや無理。7番目の問題にやたら時間がかかったんだけど、辛かったのはどの辺だろ。セオリー的にはt = tan(x/2)と置…

問題3.17の解答(Matplotlib)

昨夜サボってたグラフの表示。sympy の関数を numpy に持ち込むのに sympy.lambdify を使った。 import sympy as sym from sympy.abc import x import pylab import numpy as np def graph(f, range, nums=100): vf = np.vectorize(f) t = np.linspace(range…

問題3.19の解答(マクローリン展開)

概説微分積分の問題3.19の解答。exp(0.5)、cos(1)、log(1.1)を小数第二位まで求める問題。ラグランジュの剰余項Rn(x)の絶対値を評価する必要があるのだけど、評価方法を経験則的にやってるので一般化できてない。 import math def trunc(x): if x > 0: retur…

問題3.21の解答(ニュートン法)

概説微分積分の問題3.21の解答。x^3 + x^2 - 3 = 0 と x^4 - x - 1 = 0 を解く問題。 def f1(x): return float(x) ** 3 + float(x) ** 2 - 3 def df1(x): return 3. * float(x) ** 2 + 2. * x def f2(x): return float(x) ** 4 - float(x) - 1 def df2(x): r…

正しいのになぜかみんなが「変だ!」という問題にPerlで答えてみた

正しいのになぜかみんなが「変だ!」という問題: x,y,zを自然数とする。このとき、x=3ならばy=5になる。あるいは、y=5ならばz=8になる。 @noricoco これは良問!さすが @noricoco 先生 > RT @hyuki Perlで解答するとこうだろうなあ。 perl -e 'for my $x(0,…

今日はPRML復々習レーン kick-off meetingの日です

1年前に挫折したわけですが、一応もう一回来てみました。適当にメモします(キックオフなので打ち合わせ中心だと思いますが)。 ご挨拶 / @naoya_t さん 今日はエクストリームリーディングします 自己紹介タイム 今後は幹事役を分散したい 会場安いとことか募…

95%の信頼区間とは

10000本のクジにx本の当たりが入っているとする。ここから100本のクジを引いた結果を元に、当たりクジが何本入っているか区間推定したい。非復元抽出なので厳密にいえば100本中の当たりクジの本数yは超幾何分布に従うが、抽出する数と比較して全体数が大きい…

超幾何分布と二項分布

非復元抽出とは、有限個のものから複数個を抽出する際に、抽出したものを戻さずに2回目以降の抽出を行うこと。こうすると二回目以降の試行の確率はだんだんと変化していくことになる。復元抽出する場合は二項分布となるが、非復元抽出をすると超幾何分布とな…

二項分布とポアソン分布

二項分布は試行回数が多くなると階乗周りの計算量が多くなる。一回の事象の発生確率pが十分に小さければ、ポアソン分布で近似ができる。例えば、5枚の硬貨を投げてすべて表がでるかどうかを64回やったときの分布を二項分布とポアソン分布で比較すると、以下…

3囚人問題

こちらはモンティ・ホール問題より有名だと思う。 ある監獄にA、B、Cという3人の囚人がいて、それぞれ独房に入れられている。罪状はいずれも似たりよったりで、近々3人まとめて処刑される予定になっている。ところが恩赦が出て3人のうち1人だけ助かることに…

モンティ・ホール問題

3囚人問題は有名だけど、こちらを見かけたのは恥ずかしながら初めて。 「プレイヤーの前に3つのドアがあって、1つのドアの後ろには景品の新車が、2つのドアの後ろにはヤギ(はずれを意味する)がいる。プレイヤーは新車のドアを当てると新車がもらえる。プレイ…

あなたの圏は大丈夫? - 手続き型言語の裏に潜む罠

Monads in PerlやAllows in Perlの話では、合成compと恒等射idを以下のように定めた。 sub comp($$) { my ($g, $f) = @_; sub { $g->($f->(@_)) }; } sub id { @_ } しかし、これは厳密には圏とならない。 合成の結合則 h . (g . f) == (h . g) . f が満たさ…

今日は 関数型都市忘年会 の日です

実家に帰るついでにふらっと立ち寄ります。ってことで、札幌に向かっています。午前中は関数型都市忘年会に出席します。途中で退席予定です。

Directing AE with Arrows

@maki_daisukeさんに教えてもらったのを読んで実装してみた。 use strict; use warnings; { package AsyncArrow; use Scalar::Util qw/weaken/; use AnyEvent; use Exporter qw/import/; use Class::Accessor::Lite new => 1, rw => ['code']; our @EXPORT =…

YAPCで話さなかったこと

今回のトークでは「斜めの矢印」とか「合成」とかそういう言葉を説明に含める必要があったので圏論のことばや記法を前半で色々紹介しましたが、泥沼詳細には踏み込み過ぎないように気をつけました。その泥沼詳細にあえて踏み込んでみたい人のために、このト…

YAPCで話したこと

今回のYAPCでスピーカーデビューしてきました。スライドは以下にあります。 Monads in Perl (動画) 応募した当初は、十数名聞きにくればいいかなーと思っていたのですが、蓋を開けてみると結構な人数に聞いていただき、ほんとうにありがとうございました。今…

Catamorphism の他の例

Catamorphismを使って二分木での畳み込みを定義すると比べると関連が見えてくるかも? リストの畳み込み 自己関手Fとして、型Xを1+A*Xへ移すものをとる。1+A*ArrayRef A→ArrayRef A なる以下のF代数が始対象となる。 sub array(;$$) { @_ == 0 ? [] # type 1…

Catamorphismを使って二分木での畳み込みを定義する

高階関数がなす圏上の自己関手Fとして、型Xを A+X*X へ移すものを考える。A+X*X は具体的には、$a∈A 、$x1, $x2∈X としたとき、$a または ($x1, $x2) の形を含むもの。F代数とは、FX→X のような射をいう。例えば、以下のような射A+Int*Int→Int。 sub choose_…

「論理と計算のしくみ」が大変ためになった

読み終わったので感想です。他の方々からも良書だ、良書だと勧められましたが、結論から言うとやはり買いです。 論理と計算のしくみ萩谷 昌己 西崎 真也 前半は論理学から話を初めてゲーデルの不完全性定理までを論じます。後半はλ計算と型理論についての内…

fixed point operator による再帰的な記述の除去

論理と計算のしくみを読んでるメモ。fixed point operator があれば、再帰的な記述を再帰しない記述に直せる。再帰的な記述とは、例えば、以下のようなもの。 my $fact = sub { my $x = shift; $x <= 1 ? 1 : $x * $fact->($x - 1); }; 階乗を求める関数$fac…

Coqの証明と自然演繹の関係

「Aならば、AならばBならばB」の証明はCoq*1だと以下のように書けます。 Goal forall (A B : Prop), A -> (A -> B) -> B. Proof. intros A B. intro. intro. apply H0. apply H. Qed.なんでこれが証明になっているんでしょうか。Coqのモデルは自然演繹*2だそ…

Rubyでわかる?チューリングマシンの停止性問題

論理と計算のしくみを読んでいてチューリングマシンの停止性問題(Halting problem)の証明がしっくり来なかったので、Rubyで書いてみました。こうして書いてみると、証明のアイデアとしては単純明快です。ちなみに、Lisper のためのチューリングマシンの停止…