フィボナッチ数列は、自然界に現れる単純にして基本的な数列である。たとえば、ヒマワリの種の並びやミツバチの家系図はフィボナッチ数列を成す。 再帰 フィボナッチ数列の漸化式をそのまま Haskell で実装すると以下のようになる。 fib :: Int -> Integer f…

Applicativeスタイルの一般的な形は、以下のようになる。 f <$> m1 <*> m2 <*> m3 ... は liftM (あるいは fmap)の別名、ap は の別名だと思ってよい。ap の実装を見てみると、以下のように定義してある。 ap :: (Monad m) => m (a -> b) -> m a -> m b ap =…

フィボナッチ数列を汎関数で書く。 fib :: (Integer -> Integer) -> Integer -> Integer fib _ 0 = 0 fib _ 1 = 1 fib f n = f (n-1) + f (n-2) そして、不動点コンビネータを遅延評価を活かして以下のように定義する。(Control.Monad.Fix を import しても …

この記事の目的は、Applicative 信者による Applicative スタイルの布教です。簡潔に結論を述べると、 foo = do a <- m1 b <- m2 return (f a b) のようなコードを書きたくなったら foo = f <$> m1 <*> m2 と書きましょうということ。合い言葉は、「do と re…

GHC 7.0.1がリリースされました。しかし、このページにも書いてあるように、cabal-install が古いとバイナリパッケージのインストールは失敗します。でも、自分でビルドすれば、あなたがインストールしている cabal-install は使わないので、大丈夫です。ビ…

注：この記事の内容には、問題があるようなので、勉強して書き直す予定です。ゲーデルの不完全性定理を読んでも理解できない Lisper のために、Lisp のコードで不完全性定理を説明してみる。昨日と同様に Emacs Lisp を使うが、Common Lisp や Scheme でもコ…

停止性問題を読んでも、意味が分からなかった Lisper のために、Lisp のコードで停止性を解説してみる。使用する Lisp としては、Scheme、Common Lisp、Emacs Lisp を検討したが、Emacs Lisp が一番よいと分かったので、Emacs Lisp を使う。 名前を使った概…

以下は Alice が定義： {-# LANGUAGE TypeSynonymInstances #-} module A where type StackA = [] top :: StackA a -> a top = head pop :: StackA a -> StackA a pop = tail push :: a -> StackA a -> StackA a push = (:) move :: StackA a -> c a -> (a -…

{-# LANGUAGE TypeSynonymInstances #-} -- 以下は Alice が定義 type StackA = [] topA :: StackA a -> a topA = head popA :: StackA a -> StackA a popA = tail pushA :: a -> StackA a -> StackA a pushA = (:) -- 以下は Bob が定義 data StackB a = Ni…

プログラミングの経験はあるが、Haskell は使ったことがない人に、2時間ぐらいで Haskell のよさを教える演習のネタを考える。Haskell の代表的な利点といえば、 型による厳密なプログラミング QuickCheck によるテストケースの自動生成 Persec によるパーサ…

用意すべきもの： git パケージ名は git-core かも ビジュアライザー BSD/Linux なら gitk、Mac なら GitX github のアカウント 今回は、自分で git サーバーを上げることはしません 環境設定 git config --global user.name "名前" git config --global use…

めでたい！ 「Scheme 手習い」が復刻しました。正確に言うと、復刻ではなく、新しい版に基づいた新しい訳です。Scheme手習い作者: Daniel P. Friedman,Matthias Felleisen,元吉文男,横山晶一出版社/メーカー: オーム社発売日: 2010/10/22メディア: 単行本（…

Visual Git Reference を訳しました。その名も図解Gitです。著者の Mark Lodato さんに連絡したら、github で fork して訳を公開して下さいと言われたのでそうしたら、本家にマージされて、右上に言語メニューまで付きました。:) Git や github は、使ってい…

たとえば SSH や PGP の鍵対を生成するときには、本当の乱数が必要になる。疑似乱数ではダメだ。Unix 上で乱数を生成してくれるデバイスとしては、/dev/ramdom がある。/dev/ramdom には、真性乱数が蓄えられていて、read システムコールで必要なバイト数だ…

State モナドと疑似乱数で書いたように、遅延評価が利用できる言語では、無限数列が扱えるので、疑似乱数を使う際に状態を持たなくてもよい。その一例として、モンテカルロ法による円周率の近似を挙げてみる。XY 平面に単位円を考える。 radius :: Double ra…

Haskell で正規表現を使いたくなったとします。Haskell には正規表現のリテラルがないので、文字列リテラルで代用します。Haskell の正規表現では、メタ文字の多くがバックスラッシュを使わずに定義されています。そこで、文字列中にバックスラッシュを書く…

Real World Haskell 読書会での Maybe モナドに関する議論をまとめておきます。 case と Maybe モナドの導入には、必ずといっていいほど、Maybe が使われます。たとえば、子供をキーとして検索すると、父親を得られる DB があるとします。 type DB = [(Strin…

Haskell 初心者は括弧ばかりの Lisp のようなコードを書く。中級者になると、($) が多くなる。上級者(言い過ぎか？)になると、($) が消えて、(.) が多くなる。この記事では、上級者になるコツをちょっと教えちゃおう。 括弧だらけのコード では、以下の例に…

SenderID/SPF に加えて、DomainKeys/DKIM を実装した RPF をリリースしました。 背景 メールアドレスの詐称を判断できるようするドメイン認証には、IP ベースと署名ベースの2種類があり、それぞれに長所短所があります。 IP ベース Sender ID/SPF 転送に弱い…

Haskell の優雅さを示すためによく使われるコードは、優雅さと分かりやすさだけに特化しており、現実的には遅いことが多い。書き手は他に効率のよい実装があることを知っているのだけれど、読み手はそうではないから、後で効率が悪いと気づいて愕然とするみ…

レビューに参加した「関数プログラミングの楽しみ」が届きました。これは、関数プログラミングの入門書をいくつか読んだ人が、もっと高みを目指すための本です。関数プログラミングの楽しみ作者: Ｊｅｒｅｍｙ Ｇｉｂｂｏｎｓ ａｎｄ Ｏｅｇｅ ｄｅ Ｍｏｏｒ…

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 が未定義になっていることに気付き、倒れそうになりました。図形言語なのに、絵が描けないじゃん！しかし、なんとか踏みとどまって完成させました。誰かの役に立つかもしれないので、公開しておき…