Haskell
不動点コンビネータを使うと、どうして無名関数で再帰ができるのかを考えてみる。 名前を取り去る 以下の階乗を計算する関数 fact を考える。 fact 0 = 1 fact n = n * fact (n - 1) これは、以下のように一つの式に変形できる。 fact n = if n == 0 then 1 …
この記事は、Monad でつまづいた Haskeller のための Monad 再入門です。 Monadとは何ですか？ Monad とは、単なる型クラスの一つです。難しいという風評もありますが、それ以上でもそれ以下でもありません。この型クラスのメソッドは、return と >>= です。…
関数型言語での関数について、Haskell を用いて説明します。 関数の型 関数の型は、-> を使って書きます。例えば、Int を Char に変換する chr という関数の型は、以下のようになります。 chr :: Int -> Char 一引数の関数の型は、まぁこんなもんだと思える…
F# の |> 演算子がかっこよいので、Haskell で作ってみた。 infixl 0 |> (|>) :: a -> (a -> b) -> b a |> f = f a 以下のようにシェルのパイプのような感じで使う。 foo :: String foo = [1..100] |> map (*2) |> filter (\x -> x `mod` 6 == 0) |> sum |> …
長年の疑問の答えが Enumerator だった。今日はそんなお話です。 findを実装する Real World Haskell の第9章に UNIX の find コマンドを作る例があります。最初は安直に実装してみましょう。まず、ディレクトリの内容を得る補助関数と、ディレクトリが辿れ…
Enumerator Package - Yet Another Iteratee Tutorialは、Iteratee: 列挙ベースのI/Oよりは分かりやすいのですが、やっぱりよく分かりません。なぜなら、僕は使い方を知りたいのに、作り方が書いてあるからです。そこで、Enumerator ライブラリの使い方を簡…
たとえば、論文を書いていて、図が本文からちゃんと参照されているかを調べたいとします。LaTeX で書いているなら、\ref{} と \label{} の中の文字列を突き合わす訳です。正規表現を使えば、テキスト全体からこれらの文字列を抽出するのは簡単です。でも、Ha…
ことの起こりは Haskell night 2009 だった。パネルの司会をしてくださった赤池さんから、「Simon Peyton Jones さんが2010年4月に日本にやってくるので、日本の人達と会いたいと言っている」と相談された。Simon さんとは「ビューティフルコード」の編集で…
Parsec などが利用する再帰下降構文解析では、左再帰が無限ループに陥るという問題がある。例えば、以下の BNF で定義される数式を考える。 expr ::= expr '+' term | term term ::= term '*' factor | factor factor :: = '(' expr ')' | nat nat = '0' | '…
フィボナッチ数列は、自然界に現れる単純にして基本的な数列である。たとえば、ヒマワリの種の並びやミツバチの家系図はフィボナッチ数列を成す。 再帰 フィボナッチ数列の漸化式をそのまま 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 は使わないので、大丈夫です。ビ…
以下は 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 によるパーサ…
State モナドと疑似乱数で書いたように、遅延評価が利用できる言語では、無限数列が扱えるので、疑似乱数を使う際に状態を持たなくてもよい。その一例として、モンテカルロ法による円周率の近似を挙げてみる。XY 平面に単位円を考える。 radius :: Double ra…
Haskell で正規表現を使いたくなったとします。Haskell には正規表現のリテラルがないので、文字列リテラルで代用します。Haskell の正規表現では、メタ文字の多くがバックスラッシュを使わずに定義されています。そこで、文字列中にバックスラッシュを書く…
Real World Haskell 読書会での Maybe モナドに関する議論をまとめておきます。 case と Maybe モナドの導入には、必ずといっていいほど、Maybe が使われます。たとえば、子供をキーとして検索すると、父親を得られる DB があるとします。 type DB = [(Strin…
Haskell 初心者は括弧ばかりの Lisp のようなコードを書く。中級者になると、($) が多くなる。上級者(言い過ぎか？)になると、($) が消えて、(.) が多くなる。この記事では、上級者になるコツをちょっと教えちゃおう。 括弧だらけのコード では、以下の例に…
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 というコンテナは、失敗…
