はてなブックマーク

圏論に寄り道したら面白くなってきて、cabal-install の解読がお留守になってしまったが、ひとつは解読が cabal-install 内に収まらなくなって、GetOpt なども調べないといけなくなってきそうだったので二の足を踏んでいる状態になったからだ。圏論の方も米田のレンマくらいまでは理解しないと意味がなさそうなのでしばらくこちらの方を進めたい。 数学者でないプログラマが圏論を学習したいと思う理由の第一はIOモナドを理解したいという欲求だろう。操作的には理解できても、やはり、IOモナドとは何かということをしっかりと理解したいという不満は残る。 しかし、圏論の参考書を読み始めてから、それだけではないような気がしてきた。圏論では全てを射で表現する。Haskell のような関数型のプログラム言語もやはり全てを関数で表現するので、なにか考え方の本質の共通点のようなものがあるのではないかと

このエントリーからしばらく 『Programming with Arrows』 の解読をやっていこうと思う。リンクからダウンロードすればPDFで読むことができる。 1 Introduction 1.1 Point-free programming Haskell では引数を省略した関数を . 演算子で合成関数をつくることで関数を定義する point-free style がある。次のプログラム count w は point-free style で書かれたプログラムの例だ。文字列の中で、w と一致する単語がいくつ現れるかを計算する。 Prelude> let count w = length . filter (==w) . words 実行例 Prelude> count "a" "Consider this simple Haskell definition, of a functi

Programming with Arrows 読解　1 --- 1 Introduction Programming with Arrows 読解　2 --- 1.2 The Arrow class Programming with Arrows 読解　3 --- 1.3 Arrows as computations Programming with Arrows 読解　4 --- 2 The Arrow classes Programming with Arrows 読解　5 --- 2.2 Arrows and conditionals Programming with Arrows 読解　6 --- 2.3 Arrows and feedback Programming with Arrows 読解　7 --- 2.3 Arrows and feedback (続き） Progra

Haskell の説明を読むと、型云々の話から始まるので敬遠していたが、リスト操作に限って言えば非常に直感的で分かりやすい。これを使わないという法はない。 リスト操作で遊びながら、Haskellの癖に慣れてから、プログラムの書き方に取り組めばいいのではないだろうか。そのプログラムも、１）関数をプログラムする、２）パターン認識でプログラムする、という Haskell の特徴をつかむと、そう難しく感じられなくなってくる。 とりあえず、まずはリストをいじって遊ぶことから。どれもキー入力しているうちにすぐに覚えられるくらい直観的に理解できる。下のリストは追々充実させていくつもり。Google で　「Haskell　リスト、関数」　で調べるといろいろ出てくる。これだけの知識でも平均値くらいは計算できる。 Hugs> sum [1,2,3,4] / 4.0 2.5 Haskell のリスト操作関数 1

Haskell の存在型というのは一体どういう意味なのだろうか。文字列型や整数型なら意味がわかる。しかし、存在型の存在という言葉にどんな意味がこめられているのか見当もつかない。 探し回っていたら、GHCのマニュアルの 7.4. Extensions to data types and type synonyms というページを見つけた。このページの 7.4.5. Existentially quantified data constructors に存在型の説明が書いてあった。これを読んだら疑問が氷解した。どうも存在型 (Existetial type) の「存在 (Existential) 」というのは、述語論理学の存在量化子の「存在」らしい。たとえば、「ある自然数 n について、n * n は２５である」という命題を述語論理学の記号で書くと下のようになる。 ∃n (n ∈ N, n *

ブラウザ上でお絵描きのできる canvas 要素をjQuery で操作してみた。 まず、jQuery をインクルードした白紙のページを Google Chrome で開き、Shift + Ctrl + J で JavaScript コンソールを表示する。別のウインドウに表示されてしまったら、左下隅の四角形のアイコンをクリックすると同じWindowに表示させることができる。 最初にキャンバス要素を作成する。 $('body').append('<canvas id="sample" width=300 height=150></canvas>'); 次に canvas の２Dコンテキストオブジェクトを作る。 c=$('canvas')[0].getContext('2d'); なぜ $('canvas')[0] なのだろうと思うかもしれないが、$('canvas') で検索できるDOM要素は

手続き型言語でプログラムを作るときには、プログラムのあちこちに変数の値を印刷する printf 文を入れておくとどこでバグが発生しているのかを見つけるのに便利だ。 Haskell では入出力関係の関数は IO モナドの中でしか使えないので、手軽に print 関数を挿入して変数の値をチェックするなどということはできない。 しかし、純粋関数のプログラムの場合も中の様子を知りたい時がある。そこで、Haskell で無理やり printf デバッグをするにはどうすればいいか試してみた。 まず、最初に簡単な Haskell のプログラムの代表として、階乗のプログラムを作ってみた。 fact 0 = 1 fact n = n * fact (n-1) このプログラムは問題なく動く *Main> fact 5 120 そこで、fact の the recursive case の n の値を毎回プリン

Parsec の使い方の実例がないかと検索していたら、つぎのページを見つけた。 Simple Parsec Example: HTMangL Parsec を使って Haskell の Birs-style の文書のうち、コード部分に HTML のタグをつけ、更に特殊文字もエスケープ表現に置き換えるというプログラムだ。Parsec の基本的な使い方がわかる上に、いろいろなテクニックが洒落ていて面白い。 実は、前回までの数回分の記事は、このプログラムを読みこなすための準備だった。 コード部分だけを抜き出したものを次に示す。 module Main where import Text.ParserCombinators.Parsec eol = newline <|> (eof >> return '\n') tilEOL = manyTill (noneOf "\n") eol codeLi

Parsec の勉強もやっと式のパースを行えるところまでやってきた。Parsec で式を定義するのには便利な関数 buildExpressionParser がある。この関数は、Text.ParserCombinators.Parsec.Expr モジュールに定義されている。式の定義を考える前に、まず一般的な EBNF 記法による式の文法の定義を見てみよう。 expr ::= expr '+' term | term term ::= term '*' factor | factor factor ::= '(' expre ') | digit+ digit ::= '0' | '1' | ... | '9' これを見ると、＊の演算は＋の演算より優先度が高く、またこの演算が左結合型であることを左再帰で表している。この EBNF 記法をそのまま Parsec のコンビネータで表現するのは面

日記

『圏論は面白い』というタイトルからは、圏論を理解している人が解説をしているように見えるかもしれないが、そうではない。Haskell のモナドの使い方がわからなかったので圏論に挑んでみたが、結局は理解できなかった。しかし、圏論の参考書をわからないなりに読んでいるうちに、Haskell のプログラミングの参考になるようなアイディアに気がついたので、少し書いてみたい気がする。 Haskell のモナドを理解するためのきちんとした数学的な解説で分かりやすそうに見えるのが、『モナドへの近道・Haskell からの寄道』という記事だ。以下の記事は、この記事からの引用ですすめていきたい。 上の参考書の最初の『基礎知識の準備』のセクションの冒頭に出てくる定義が「メタグラフ」の定義だ。以下に引用する。定義 1 (メタグラフ metagraph) メタグラフは射 (arrow) と対象 (object) とい

edit.rb を使うと、irb 上で Ruby のプログラム開発ができるようになったので、irb から出るのが面倒くさくなった。それで、irb を shell として使う方法はないかといろいろと考えてみた。 まず、カレントディレクトリを表示してみた。 C:\Users\ganesh>irb irb(main):001:0> Dir.pwd => "C:/Users/ganesh" カレントディレクトリを変更した。 irb(main):002:0> Dir.chdir 'Ruby' => 0 カレントディレクトリのファイルのリストをとった。 irb(main):003:0> Dir.glob '*' => ["a.txt", "aa.txt", "aminoacid.rb", "aminoacid.txt", "array_grep.rb", "c2r.rb", "code.rb", "c

Haskell のIOモナドの分かりにくさに対する批判に対し、フィリップ・ワドラーが、「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも？」と答えたそうだ。これで、すんなり納得するのはよほど圏論に詳しい人だろう。 管理人としては、圏論抜きで Haskell というプログラム言語を使えればそれが一番ありがたいのだ。しかし、最低でもモナドや圏論やモノイド対象が何を指しているのかくらいは知っておきたい。そこで、『モナドへの近道・Haskell からの寄り道』（中村翔吾著）というレポートを道案内にして、少なくともモナドというのが何を指しているのかを探索してみた。 まず、圏論の「圏」という言葉が何を指しているかだ。端的に言うと圏とは、対象と射からなる構造だ。集合と写像なら少しは馴染みがあるので、集合に例えると、対象とは集合のことで、射とは写像のことだ。集合 a と集合 b があり、そ

Ubuntu で Hugs をインストールしてから思いがけずはじめてしまった Haskell の探検だが、そろそろ脳が飽和状態になったのでここらでいったんお休みにしたい。何となく Haskell に取り組むときのコツのようなものが分かった気がするのでまとめてみる。 １）　Haskell の処理するデータは基本的にはリスト（木構造も含めて）である。リストに表せるデータなら、非常に簡潔にデータの定義ができる。プログラムはデータ構造とアルゴリズムだという言葉があるが、Haskell ではデータ構造の定義が簡単にできる。 ２）　Haskell がデータを処理するときの基本的な道具は、再帰である。再帰的な定義や関数に習熟すれば非常に簡潔で凝縮したプログラムを書くことができる。また、遅延評価は無限数列を使えるようにするための工夫だと割り切ると、無限数列を気軽に使えるありがたさが分かる。 ３）　Hask

Real World Haskell　を読み始めたが、GHCを使う想定になっていたので、The Haskell Platform からダウンロードした。今のところWindows7上でも問題なく動いている。 インストールすると、スタートメニューに GHCi のアイコンが登録される。アイコンをクリックすると、GHCi　が起動するが、そのままでは、:edit で編集したプログラムを :load でロードできない。そこで、:cd コマンドで、パーミッションのあるディレクトリにカレントディレクトリを変更する必要がある。 Prelude> :cd C:\Users\user_name\Documents\Haskell これで、Real World Haskell のサンプルを　:edit コマンドで作成して、:load コマンドで GHCi に読み込むことができるようになる。ただし、Hugsとは操作

PEG (Parsing Expression Grammar) も 文脈自由文法もプログラム言語の文法を定義する方法だ。おまけに、どちらも再帰下降構文解析という手法で実装することができるので、一体どこが違うのかが分り難い。 そこで、原点に返って構文解析とはどのようなことをするのかを考えてみよう。プログラムのソースファイルに書き込まれているプログラムは単なる文字コードの並びが延々とづづいているだけだ。アルファベットを延々と書き並べられた紙のテープを渡されて解読しなさいといわれているようなものだ。 これでは取り付く島がないのでどうするかというと、このテープを単語などのまとまりごとに、小さく切っていく。この作業をしても単に単語が順番に並んでいるだけでは、意味不明だ。この単語の並びを関連ある物ごとに並べたり、関連性の階層を調べたりして、単語どうしの関連性の構造を見つけなければならない。この木構造

Ubuntu では root 権限で作業をするときは sudo を使う。いちいち sudo とタイプするのが嫌だったので su で root になろうとしたら、どんなパスワードを入れても認証失敗になってしまう。 不審に思ってネットで検索したら、Ubuntu ではそもそも root のパスワードは設定されていないとのことだった。 su と同じ操作をするためには、 sudo -i と入力するらしい。 Ubuntu の特徴に慣れるのにしばらくかかるかもしれない。

抽象的な記号を扱うときに大切なのは、それについての何か具体的なイメージを持っていることだ。 例えば集合のイメージなら丸い輪のなかに色とりどりのおはじきが入っているところを想像するし、関数のイメージは、二つの集合の要素のおはじきを糸で結んだ物が、おはじきの数だけあるところをイメージすると分かりやすい。 このイメージモデルを使えば、写像 f : A -> B が全射なら、集合Bのどのおはじきをつまみあげても、その端に集合Aのおはじきが付いてくるし、単射なら、集合Aのおはじきを二つ引っ張ると、必ずBの違うおはじきが引っ張られる。 全単射なら、集合Bのどのおはじきにも集合Aのおはじきはつながれており、集合Bの違うおはじきに対しては集合Aの同じおはじきが付いてくることはない。もしそうでなければ、集合Bの二つのおはじきにひとつの集合Aのおはじきがつながっていることになり、写像の条件を満たさないし、集合

日記

Hugs で Haskell のプログラムを作る練習をしようと思っても、いちいちファイルに作成するのが面倒だ。次のワンライナーなら Hugs のコマンドラインから実行できるので、何回も打ち込んで試しているうちに自然に Haskell の使い方が身につく。 練習用の一行プログラムは、階乗・フィボナッチ数・素数・順列・組み合わせ・配列の長さ・クイックソート・要素の挿入・Maybeモナド・IOモナドの10のプログラムだ。これらを毎日1回空で作成できるようになれば、Haskell はかなり楽しくなる。 階乗の計算（基本的な再帰関数） Hugs> fact 5 where fact 0 = 1; fact n = n * fact (n-1) 120 フィボナッチ数（：演算子と tail と高階関数 take, zipWith の使いかた） Hugs> take 10 fib where fib =

初心者がHaskell をちょっとした思考実験に使えるようになるまでのチェックリストを考えてみた。自分でもまだ達成していない事柄も多いので、これからの学習の目標のようなものだ。 Hugs のインストール Hugs の起動と終了。Linux の場合は、hugs -Evi または hugs -Egedit のように -E オプションでエディタを指定できる。 Hugs で数式の値を求めることができる。(1+2)*３ の答えを出すようなこと。 sqrt, mod, sin など標準の関数を使うことができる。また、1+2 と (+) 1 2、mod 4 3 と 4 `mod` 3 のように演算子や関数を前置型や中置型にして使うことができる。 リストやリストのリストを作成できる。リストの要素はすべて同じ型でないといけないことを理解できる。 Hugs でリストの操作をする。(:), ++, head,

ubuntu に Xampp for Linux をインストールした。 apache2 が先にインストールされていると衝突がおきるので、アンインストールするか、サーバを止めておいた方がよい。 上のサイトから xampp-linux-1.6.6.tar.gz をダウンロードしてきたら、ファイルをデスクトップからホーム・フォルダに移し、 sudo tar xvfz xampp-linux-1.6.6.tar.gz -C /opt で /opt ディレクトリに解凍するとインストールはおしまい。 sudo /opt/lampp/lampp start で、サーバが立ち上がるので、ブラウザで http://localhost をアクセスするとウェルカムメッセージ画面が表示される。 サーバを止めるときは、 sudo /opt/lampp/lampp stop パッケージのアンインストールも、 sudo