関数型言語 Haskell |
作成日： 2006-10-01 最終更新日： |
青木峰郎氏の「ふつうのプログラマのための Haskell 入門」を借りた。 また、向井淳氏の「入門 Haskell」も借りた。 どういうわけか、2つとも同じ図書館にあったのである。 それらをもとに、少しずつ Haskell のことを書く。
私は、Vine Linux を使っている。 Vine Linux 純正の配布パッケージはない。 そこで、インストールは、 http://haskell.org/ghc/download.html から、Current Stable Release (私がインストールした時は 6.4.2) の Linux(x86) の RedHat Linux/x86 9.0 RPMs (base RPM) を使った。 普通の rpm と同様にインストールして、順調に動作している。
その後、わけあって Windows XP を使っている。こちらでも順調に動作している。
現在では、上記 GHC を素でインストールするより、Haskell Platform (http://www.haskell.org/platform/) をインストールすることが勧められているので、私もそれに従う。 インストーラの容量は100MB 強である。 (2013-06-01)。
さらにそのあとは、64 bit 版を Windows 版 8.1 にインストールした(2014-12-14)。
頭から練習問題を解いていくのが苦手なので、 気に入った問題から行うことにする。まずは、 向井氏の「入門 Haskell 」から。
86 ページの格子点列挙問題を考えてみよう。 ２次元の格子点列挙問題はわかった。 次のページの 87 ページにある、 任意の n 次元の格子点に対応する列挙はどうするか。
２次元の場合はタプルで対を作っていたが、 n 次元のへの拡張では、タプルでは難しい。 リストにすべきだろう、そこまではわかった。
それから先は苦労した。 ヒントに従って、再帰を使ってコードを書いてみた。
lattice d n = [i : lattice (d-1) (n-i) | i <- [0..n]]
lattice 1 n = [n]
all_lattices d = concat [ lattice d i | i <- [0..] ]
結果は失敗。エラーメッセージは次の通り
lattice.hs:1:15:
Occurs check: cannot construct the infinite type: t = [t]
Expected type: t
Inferred type: [t]
In the expression: i : (lattice (d - 1) (n - i))
In the expression: [i : (lattice (d - 1) (n - i)) | i <- [0 .. n]]
Failed, modules loaded: none.
どうやら言いたいのは、こういうことのようだ。
Occurs check: 有限型: t = [t] を構成できない 期待される型: t 推論される型: [t]
といっても、わけがわからない。悪戦苦闘して、 結局自力でわからなかったので、Web で確認した。 あ！なるほど。次のように書けばよかった。
lattice 1 n = [[n]]
lattice d n = concat [map (i:) (lattice (d-1) (n-i)) | i <- [0..n]]
all_lattices d = concat [ lattice d i | i <- [0..] ]
まず、順番が違う。最初に lattice 1 n の定義が必要。 そこでは、[n] ではなく、[[n]] が必要。 初版本の記述は誤植。
次に、lattice d n の定義では、 数字を（再帰した）リストに直接 : によって先頭に挿入しようとする、 バカなことを考えていた。当然、map が必要だ。 concat は、型を合わせるためである。
では、今までに習ったことをもとにして、どこまで記述できるのかを確かめよう。 m 行 n 列の行列 a(m, n) に対して、次を求める。
仮定として、行列はリストのリストで構成されているとする。 全要素の平均は、次の通りでいいだろう。
average xs = sum xs / fromIntegral (length xs) matrixAverage xs = average (concat xs)
行列はリストの入れ子になっているので、平均を求めるためにリストの入れ子をはずす。 このときの関数が concat であるのに気付かなかった。 最初、ruby からの類推で flatten という名称かと思ったのだが、 そのような名前の関数は Haskell にない。 探し方に困ったが、関数定義が [[a]] -> [a] であるはずだから、 検索のキーワードに [[ と入れてみた。そこで、見事 concat だとわかった。
次は、１行（１列）の要素の和はどうだろう。
rowSum xs = map sum xs columnSum xs = map sum (transpose xs)
行の和は、map を適用すればよい。列の和は、transpose にまかせた。 計算効率のことは考えていない。 １行（１列）の要素の平均と、全要素の平均の差はどうだろう。
rowResidue xs = map (\x -> x - matrixAverage xs) (map average xs)
columnResidue xs = transpose xs
これでよいはずだ。そのほか、ついでに二つのリストをベクトルとみなしたときの 内積を定義しよう。
innerProduct xs ys = sum (zipWith (*) xs ys)
ここまでやっておけば大丈夫だろう。
エラトステネスのふるいとは、素数をもとめるアルゴリズムとしてよく知られている。 Haskell では次の実装が知られている。
primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
これを応用して、メビウス関数をすっきりと求める方法が Haskell にはあるのではないかと思い、 考えたり調べたりしたが、なかなかみつからない。
まりんきょ学問所 ＞ 関数型言語手習い ＞ 関数型言語 Haskell
