素数判定 - あどけない話
要約：素数判定に使われるミラーラビン法を解説しながら、Haskell で実装してみる。 フェルマーテスト 大きな数を確実に素数だと判定するには、大変時間がかかるので、実用的には「ほぼ素数だ」と確率的に判定する。確率的な素数判定の代表格がフェルマーテストである。 フェルマーテストには、以下に示すフェルマーの小定理を利用する。 a^p ≡ a (mod p) a は任意の整数。p は素数である。法 p の下で a を p 乗したものは、a と合同であると言う意味だ。a には制限はないが、特に a を p より小さい整数、0 ≦ a ≦ p - 1 とすれば、a を p 乗して、p で割ると a に戻るとも解釈できる。 最初に見たときは、だからどうしたと思われるかもしれない。しかし、有名なフェルマーの大定理が実用上何の役にも立たないのに対し、フェルマーの小定理はいろんな場面で活躍する。 実際に計
賢人鳥 - あどけない話
分かった！ 分かった！ 分かった！ 自己言及 ものまね鳥(M)は、自己言及する鳥なんだ！ Haskell では、型推論がジャマして、ものまね鳥を実現できない。 -- Mx = xx m x = x x -- エラーになる ヒバリ(L)も実現できない！ -- Lxy = x(yy) l x y = x (y y) -- エラーになる 当然の帰結として、Haskell では再帰を使わないと賢人鳥(Y)を実現できない！ 賢人鳥1 wikipediaの Y コンビネーターに書かれている最初の賢人鳥はこう。 (define Y (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))) これは SLL だ！ ;; Sxyz = xz(yz) (define S (lam
正規表現を超える - あどけない話
まずは、Audrey さんが言った Haskell の殺し文句を思い出して頂きたい。 正規表現ベースのパーサはメンテナンスしにくいのに気づいた？ Parsec を使って 15分で Perl6 の完全なパーサを書く方法を勉強しましょう。 15分というのは誇張が入っていると思うが、正規表現が保守しにくく、Haskell の Parsec は強力で保守し易いのは事実だ。その理由を Perl と Haskell のコードを示しながら説明してみたいと思う。 Perl を愛する方に：この記事は Perl を攻撃するために書いたのではない。Perl を選んだのは、正規表現を広めた言語であり、僕がそれなりに Perl のコードを書けるためである。この記事の目的は、正規表現よりも関数型パーサー(Parsec)の方が優れていると示すことだ。 例題 この記事では例題として、IPv4 アドレスを解析する関数を書く
最高のHaskell入門書 - あどけない話
輪講で「Programming in Haskell」をようやく読み終えました。この本は、最高のHaskell入門書といって間違いないでしょう。 Programming in Haskell 作者: Professor Graham Hutton出版社/メーカー: Cambridge University Press発売日: 2007/01/18メディア: ペーパーバック購入: 2人 クリック: 67回この商品を含むブログ (22件) を見る 一緒に Haskell の本を何か読もうという話が、友達との間で出たとき、最初は「The Craft of Functional Programming」にしようかと思っていました。ただ、出版社の人から「Programming in Haskell」を勧められたことがあったので、二冊を友達に提示したところ、直感で「Programming in Has
文章の書き方 - あどけない話
2006年に IIJ の新人研修で「文章の書き方」という講義を担当しました。そのときの資料を何人もの人に個別に差し上げていたのですが、それも面倒になってきました。新人研修の担当者に問い合わせたところ、公開しても問題ないとのことでしたので、資料を公開します。 「文章の書き方」の資料
TLSのひみつ - あどけない話
書くと約束したのは、かれこれ1年半前でしょうか。書こうと思えば、すぐ書ける内容でしたが、結婚の準備におわれてうやむやになったままでした。 まだ書いてほしいとのことだったので、2ヶ月ぐらい前に書きました。3月7日に公開されていたとは知りませんでした。orz TLSのひみつ： SSL（Secure Socket Layer）はラッパー（トンネル）として実装できるが、TLS（Transport Layer Security）はラッパーとして実装できないと勘違いしているエンジニアが多い。この記事では、（少なくともクライアント側では）TLS がラッパーとして実装でき、アプリケーションプログラムの実装を変更しなくても TLS が利用できることを示す。 率直にいって、僕は TLS は IETF の(数多い)失敗の1つだと思います。SSL の方が、遥かに優れています。 ただ、TLS の設計思想自体が誤解さ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
