あどけない話

Internet technologies

2010-05-01から1ヶ月間の記事一覧

多相再帰型

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 で破壊的なヒープソート

ST モナドの中では、配列に対して破壊的な操作ができるので、試しにヒープソートを作ってみました。ヒープソートのアルゴリズムは、「珠玉のプログラミング」を参考にしました。 > x <- randomArray 10 100 > x array (1,10) [(1,71),(2,27),(3,85),(4,6),(5…

リストは非決定性のモナド

Haskell のリストはモナドであり、それは非決定性の文脈を表すと言われます。しかし、そのことを扱った例題は少なくて、しかもイマイチでした。そこで、Scheme で書かれたよい例題を Haskell で書き直してみました。「On Lisp」の「非決定性」の章では、謎め…

Monadとして抽象化すると何が嬉しいの?

The Typeclassopediaには、以下のような文章があります。 結局、あらゆる誇大広告にもかかわらず、Monadは単なる型クラスに過ぎません。 また、The Trivial Monadでは、以下のように述べられています。 Haskell の Monad は型クラスの1つです。Haskell の型…

Applicative よりも Monad の方が力が強い理由

Applicative よりも Monad の方が力が強い理由を考えるためのメモ。これから議論するためのたたき台なので、そう思って読んで欲しい。 コンテナで包む return Monad とは、コンテナである。コンテナは、文脈を表す。たとえば、Maybe というコンテナは、失敗…

SICP の図形言語

SICP の図形言語を Haskell で書いていて、最後に draw-line が未定義になっていることに気付き、倒れそうになりました。図形言語なのに、絵が描けないじゃん!しかし、なんとか踏みとどまって完成させました。誰かの役に立つかもしれないので、公開しておき…

Haskell で Y コンビネータ

Haskell では、Y コンビネータが作れないと誤解している人がいるので、できることを示すと同時に、これまで学んだことをまとめてみます。 遅延評価を活かした Y コンビネータ 関数名を用いた再帰を使ってよいなら、Haskell では遅延評価のおかげで、Y コンビ…

「プログラミングHaskell」の増刷

おかげさまで「プログラミングHaskell」の増刷が決まりました。第1版第1刷の誤植表に載っていない間違いを発見した人は、今すぐ報告していただけると助かります。間に合えば、第2刷に反映したいと思います。プログラミングHaskell作者: Graham Hutton,山本和…

Parsec2と3

GHC 6.10 に付随していた Parsec のバージョンは 2 だ。現在の Parsec のバージョンは 3 であり、以下のような特徴がある。 モナド変換子として実装されているので、下回りを自由に変更できる。 ByteString をモナドのインスタンスにすることで、入力に Byte…