Haskell の優雅さを示すためによく使われるコードは、優雅さと分かりやすさだけに特化しており、現実的には遅いことが多い。書き手は他に効率のよい実装があることを知っているのだけれど、読み手はそうではないから、後で効率が悪いと気づいて愕然とするみ…
レビューに参加した「関数プログラミングの楽しみ」が届きました。これは、関数プログラミングの入門書をいくつか読んだ人が、もっと高みを目指すための本です。関数プログラミングの楽しみ作者: Jeremy Gibbons and Oege de Moor…
twitter で続いている Haskell と副作用、および参照透明性の議論ですが、twitter ではコードを示しにくいので、ブログに書きます。これに対する返答は、twitter でも構いませんし、ブログに対するコメントでもいいですし、トラックバックでも OK です。多く…
不動点 関数 f :: a -> a に対して、f x == x となる x を「関数 f の不動点」という。もし、関数 f を入力として取り、関数 f の不動点を返す関数 Y があるとすれば、関数 f の不動点を Y f と表現できる。ここで、Y の型を調べる。引数 f の型は a -> a、Y…
Data.Sequence で使われている FingerTree の構造を調べていて、多相再帰型を初めて知った。僕が思いつく最も簡単な例はこう。 data Bin a = Bin a a deriving Show data List a = Nil | Cons a (List (Bin a)) deriving Show こういう風に使う。 → Nil Nil …
ST モナドの中では、配列に対して破壊的な操作ができるので、試しにヒープソートを作ってみました。ヒープソートのアルゴリズムは、「珠玉のプログラミング」を参考にしました。 > x <- randomArray 10 100 > x array (1,10) [(1,71),(2,27),(3,85),(4,6),(5…
Haskell のリストはモナドであり、それは非決定性の文脈を表すと言われます。しかし、そのことを扱った例題は少なくて、しかもイマイチでした。そこで、Scheme で書かれたよい例題を Haskell で書き直してみました。「On Lisp」の「非決定性」の章では、謎め…
The Typeclassopediaには、以下のような文章があります。 結局、あらゆる誇大広告にもかかわらず、Monadは単なる型クラスに過ぎません。 また、The Trivial Monadでは、以下のように述べられています。 Haskell の Monad は型クラスの1つです。Haskell の型…
Applicative よりも Monad の方が力が強い理由を考えるためのメモ。これから議論するためのたたき台なので、そう思って読んで欲しい。 コンテナで包む return Monad とは、コンテナである。コンテナは、文脈を表す。たとえば、Maybe というコンテナは、失敗…
SICP の図形言語を Haskell で書いていて、最後に draw-line が未定義になっていることに気付き、倒れそうになりました。図形言語なのに、絵が描けないじゃん!しかし、なんとか踏みとどまって完成させました。誰かの役に立つかもしれないので、公開しておき…
Haskell では、Y コンビネータが作れないと誤解している人がいるので、できることを示すと同時に、これまで学んだことをまとめてみます。 遅延評価を活かした Y コンビネータ 関数名を用いた再帰を使ってよいなら、Haskell では遅延評価のおかげで、Y コンビ…
おかげさまで「プログラミングHaskell」の増刷が決まりました。第1版第1刷の誤植表に載っていない間違いを発見した人は、今すぐ報告していただけると助かります。間に合えば、第2刷に反映したいと思います。プログラミングHaskell作者: Graham Hutton,山本和…
GHC 6.10 に付随していた Parsec のバージョンは 2 だ。現在の Parsec のバージョンは 3 であり、以下のような特徴がある。 モナド変換子として実装されているので、下回りを自由に変更できる。 ByteString をモナドのインスタンスにすることで、入力に Byte…
Haskellers Meeting 2010 Spring で発表した僕のスライドを以下のように公開しました。 Haskell で Web サーバーを実装してみました Experience on implementing a Web server in Haskell
Snow Leopard で Emacs 22.3 がコンパイルできなかったので、コンパイルできるようにしたソースを、Gitoriusで公開しました。Macports のパッチとか、inline パッチとか、Goby の View モードでウインドウタイトルが消えるハックとかが入っています。詳しく…
Haskellers Meeting 2010 Springで、Simon さんに STM(Software Transaction Memory)の話をして頂くようにお願いしました。参加者の人があらかじめ予習できるように、参考書として Real World Haskell とビューティフルコードを挙げておきました。Real World…
Simon Peyton-Jones will visit to Tokyo on 16 April 2010. So, we will organize a small conference among Haskell community in Tokyo. Three presentations including Simon's one will be given. Please register yourself on ATND (written in Japane…
4月16日に、Haskell 界の大御所 Simon Peyton-Jones さんが東京にやってきます!彼のお話を聞きたい人は、今すぐ ATND で参加表明して下さい。
重い腰を上げて、3つのソースを公開しました。 Piki Pikiのソースを github で公開し、Pikiバージョン0.3.0をHackageに登録しました。バージョン0.2からの機能追加はありません。Cabal に対応したことと、Applicative スタイルに直せるところは直したことが…
Haskell で書いた HTTP サーバー Mighttpdをリリースしました。Mighty (マイティー)と読みます。興味のある人は、遊んでみて下さい。これまで Mew.org は Apache で運用してきましたが、すでに Mighttpd に置き換えています。
要約:素数判定に使われるミラーラビン法を解説しながら、Haskell で実装してみる。 フェルマーテスト 大きな数を確実に素数だと判定するには、大変時間がかかるので、実用的には「ほぼ素数だ」と確率的に判定する。確率的な素数判定の代表格がフェルマーテ…
IIJ 社内でやったチュートリアル 純粋関数型言語Haskellの紹介 〜制約プログラミングのススメ〜 の資料を公開しました。
正規表現を超えるの補足として、CSVファイルを例に挙げて考えてみる。CSVファイルの定義は、RFC4180にある。 file = record *(CRLF record) [CRLF] record = field *(COMMA field) field = (escaped / non-escaped) escaped = DQUOTE *(TEXTDATA / COMMA / C…
Parsec には以下のようなコンビネーターが存在する。 many p -- p を 0 回以上 many1 p -- p を 1 回以上 count n p -- p を n 回 しかし、正規表現の"{min,max}"のような範囲指定はない。そこで実装してみた。 import ApplicativeParsec range :: Int -> In…
haskell-jp にアナウンスしましたが、読んでいないという人がいるようなので、こちらにも書きます。2009年忘年会のWikiページができています。参加者には全員発表してもらいますので、各自テーマを選んで下さい。
よく、Haskellには副作用がないと言われるが、それは間違いだ。確かに、Haskell には状態の変化(あるいは再代入)という副作用はない。しかし、入出力という副作用はある。この記事では、Haskell の副作用に対して、命令型プログラマーにすっきりと理解でき…
GHC に -ddump-simpl オプションを渡すと、Core 形式(中間表現の関数型言語)を出力するというので、Performance/Accumulating parameterのコードに対して Core を出力しみた。 len 末尾再帰でない len のコードはこう。 len :: [a] -> Int len [] = 0 len …
中村正三郎さんがプログラミングHaskellの書評を書いてくれましたので、触発されて少し補足します。 訳について 直訳を避け、意訳する 訳は、直訳を避け意訳を心がけました。原文が想像できない自然な日本語を目指しています。たとえば、章のはじめには必ず…
遅延評価では再帰の効率はどうなるかという問題です。Real World Haskell で、末尾再帰は重要だと言った後に、遅延評価では末尾再帰なんて気にするなとちゃぶ台を返しています。ようやく haskell-cafeで答えを見つけたので、Luke Palmer さんの許可を得て訳…