「ほっ」と。キャンペーン

<   2009年 08月 ( 73 )   > この月の画像一覧

Haskell ワンライナー

Hugs で Haskell のプログラムを作る練習をしようと思っても、いちいちファイルに作成するのが面倒だ。次のワンライナーなら Hugs のコマンドラインから実行できるので、何回も打ち込んで試しているうちに自然に Haskell の使い方が身につく。

練習用の一行プログラムは、階乗・フィボナッチ数・素数・順列・組み合わせ・配列の長さ・クイックソート・要素の挿入・Maybeモナド・IOモナドの10のプログラムだ。これらを毎日1回空で作成できるようになれば、Haskell はかなり楽しくなる。

階乗の計算(基本的な再帰関数)
Hugs> fact 5 where fact 0 = 1; fact n = n * fact (n-1)
120

フィボナッチ数(:演算子と tail と高階関数 take, zipWith の使いかた)
Hugs> take 10 fib where fib = 0:1:zipWith (+) fib (tail fib)
[0,1,1,2,3,5,8,13,21,34]

素数(リストの再帰関数、リストの内包的定義、$演算子の使いかた)
Hugs> take 10 $ sieve [2..] where sieve (x:xs) = x:sieve [y|y <- xs, y `mod` x /= 0]
[2,3,5,7,11,13,17,19,23,29]

順列(多分木の再帰関数、内包的定義のパワー。注意:delete が Prelude の標準関数ではないので、Hugs のコマンドラインで :load List としてListモジュールに移動する必要がある。)
List> perm "abc" where perm [] = [[]]; perm xs = concat [map (x:) $ perm (delete x xs)| x <- xs]
["abc","acb","bac","bca","cab","cba"]

組み合わせ(引数が複数の時の再帰関数)
Hugs> comb "abc" 2 where comb _ 0 = [[]]; comb [] _ = []; comb (x:xs) n = map (x:) (comb xs (n-1)) ++ comb xs n
["ab","ac","bc"]

配列の長さ(ワイルドカードの使いかた)
Hugs> mylength [1,2,3] where mylength [] = 0; mylength (_:xs) = 1 + mylength xs
3

クイックソート(左右の再帰)
Hugs> qsort [2,5,8,1] where qsort [] = []; qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)

要素の挿入(let の使い方)
Hugs> insertAt 'X' "abcd" 2 where insertAt x xs n = let(ys,zs) = splitAt n xs in ys ++ [x] ++ zs
"abXcd"

Maybe モナド(モナドのプログラム)
Hugs> Just 2 >>= double where double x = return (x + x)
Just 4

IOモナド(入出力の基本)
Hugs> do cs <- getLine; putStrLn cs
hello, world
hello, world

その他のワンライナー

ファイルの書き込み
Hugs> writeFile "hello.txt" "hello, world"

ファイルの読み込み
Hugs> do cs <- readFile "hello.txt"; putStr cs
hello, world

データのシリアライズ
1.書き込み
Hugs> writeFile "array.txt" (show [1,2,4,6,7])

Hugs> readFile "array.txt" >>= putStr
[1,2,4,6,7]

2.読み出し
Hugs> do cs <- readFile "array.txt"; print $ sum ((read cs)::[Int])
20
[PR]
by tnomura9 | 2009-08-31 23:18 | Haskell | Comments(0)

やさしい Haskell 入門

Haskell と格闘を始めてから1か月。やっと「やさしい Haskell 入門」を読んでも意味が分かるようになってきた。

何となく Haskell の全体像が見えてきた。あとは、コツコツとサンプルを集めて動かしてみるしかない。何回もこれでおしまいと言いながら続けてきた Haskell 記事だが、モナドの端っこまで何とかたどり着いた気がするのでこれで本当のおしまい。

1か月も同じテーマでブログを書き続けるのは正直しんどかった。しかし、書くことによって、理解できた部分も多い。このブログで掲載したサンプルは、動作確認済みなので活用していただければ幸いだ。

Haskell は本を読んで勉強しようとすると大変だし、きちんと理解するのは素人には不可能だが、動かしてみると意外にわかりやすい。「使ってみれば、やさしい Haskell 」という感覚を伝えたくてこの一連の記事を書いた。

Haskell は面白い。
[PR]
by tnomura9 | 2009-08-29 10:33 | Haskell | Comments(0)

Maybe モナドのプログラミング

モナドについていろいろ抽象的に考えてもプログラムは書けないので、モナドのデータ型の中で一番わかりやすそうな Maybe モナドを使ったプログラムをつくってみた。

ます、Maybe モナドがどんなものかを知るために、Maybe モナドを戻り値に戻す lookup 関数の動作を見てみる。lookup 関数は、第1引数の値が、第2引数のタプルのリストの中のタプルの第1要素と一致すれば、そのタプルの第2要素を Just x の形で返し、一致が見られなかった場合は、Nothing をかえす。文章で表すより使ってみた方が早いので、以下に示す。

Hugs> lookup 1 [(1,2),(3,4)]
Just 2
Hugs> lookup 0 [(1,2),(3,4)]
Nothing

そこで、このような Maybe モナドがどのように定義されているのか見てみる。

Hugs のコマンドプロンプトで次のように入力すると、

Hugs> :find Maybe

エディターに、Prelude の内容が表示されるはずだ。そこで、maybe を検索していくと次のような記述を見つけることができる。

-- Maybe type ---------------------------------------------------------------

data Maybe a = Nothing | Just a
deriving (Eq, Ord, Read, Show)

maybe :: b -> (a -> b) -> Maybe a -> b
maybe n f Nothing = n
maybe n f (Just x) = f x

instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

instance Monad Maybe where
Just x >>= k = k x
Nothing >>= k = Nothing
return = Just
fail s = Nothing

第1段落を見ると、Maybe のデータ型が、Nothing と Just x であることが分かる。第4段落には bind 演算子 >>= の定義がある。これを見ると、Just x が >>= をはさんで 関数 k に渡されたときは、k x が実行され、Nothing が k に渡されると、Nothing が返されることがわかる。Nothing が渡されると k がどんな関数でも Nothing が返えるので、実質的には Just x が関数 k に渡されたときだけを考えてプログラムすればよい。

そこで、lookup の戻り値である Maybe モナドを受け取って、Maybe モナドがたのデータを返す testmaybe 関数をプログラムしてみる。testmaybe 関数が Maybe モナドを受け取ると言っても、>>= の定義を見ると関数 k には Just のデータ部分の x が渡っているので、testmaybe の型は、Int -> Maybe Int の形にすることになる。Just x から x を受け取った testmaybe が x を2倍して Just n の形で返すようにするには、次のようにプログラムする。

Hugs> :e testmaybe.hs

(testmaybe.hs の内容)
testmaybe :: Int -> Maybe Int
testmaybe x = return (x * 2)

それでは、こうして作った Maybe モナドの世界の新しい住人 testmaybe を動かしてみよう。

Hugs> :l testmaybe.hs

まず、単純に Just 1 という Maybe モナドのデータを testmaybe に渡してみる。
Main> Just 1 >>= testmaybe
Just 2
Just 1 のデータが Just 2 になって帰ってきているのでうまくいったようだ。それでは Nothing ではどうだろう。

Main> Nothing >>= testmaybe
Nothing

ちゃんと Nothing が返ってくる。それでは、lookup の戻り値を受けて見よう。
Main> lookup 1 [(1,2)] >>= testmaybe
Just 4

また、testmaybe の戻り値を次々に testmaybe につなげていくこともできる。
Main> testmaybe 1 >>= testmaybe
Just 4
Main> testmaybe 1 >>= testmaybe >>= testmaybe
Just 8

このように、モナドの理論は難しいが、モナドの世界の住人を増やすのは意外に簡単だった。

モナドの世界でプログラミングをする限りは、関数がモナドの外の世界に影響することはないのでモジュール化されたプログラムを気楽に作ることができる。また、関数と関数を結び付ける bind 演算子 (>>=) のおかげで、要素的な働きをする関数を定義しておくと、複雑な処理も関数の結合だけで実現できてしまう。たとえば Maybe モナドの場合、データの取得が失敗した場合の if then else 制御文による記述を個々のプログラムで行う必要がなくなるのですっきりした処理の記述になる。

IO処理のために仕方なくモナドの世界のプログラムをするのではなく、積極的にモナドのプログラムを活用すると便利なのかもしれない。もちろん、もう少し Haskell が分かってからの将来の話になるが。
[PR]
by tnomura9 | 2009-08-29 07:56 | Haskell | Comments(0)

モナドとの付き合い方。

モナドの本当の意味を理解しようとすると、圏論の概念や定理に対する正確な理解が必要だが、それは、不可能に近い。それにもかかわらず、データを表示したり、ファイルの読み書きなどIOモナドを使ったプログラムを書くことはできる。要するに、正確な理解はできなくてもプログラムは動くのだ。それに、使っているうちにモナドの振る舞いが何となくわかってきてモナドの利点を利用したプログラムが書けるようになるかもしれない。

ただ、モナドを使ったプログラムをするときに気をつけておいたほうが良い点がありそうなので書いてみた。もちろんモナドを圏論的に理解しているとは言えないのであくまでも印象だ。

1.モナドの大きな特質は、一連のプログラムとデータのカプセル化だ。たとえば、IOモナドの中で使う関数は、IOモナドを引数にとり、IOモナドを戻り値として戻す。つまり、IOモナドに関連する関数はIOモナドの世界から抜けられない。したがって、IOモナドの中で定義されている関数の戻り値を普通の関数が利用するにはインターフェースがいる。

2.Bind 演算子( >>= ) の働きは関数の結合であるが、通常の関数の合成を拡張した働きを持っていることが多い。たとえば、Maybe モナドは、Nothing と Just a の2種類のデータを次の関数に伝達することができるし、IOモナド型の bind 演算子は、関数の実行される順序を保つように設計されている。また、この演算子をモナド内で利用することで、関数を結合してそのモナド内で働く新しい関数を簡単に作り出すことができる。

3.Return 関数は、定義としてはモナド内の単位元で、恒等関数だが、普通の関数の世界の値をIOモナド内に移すインターフェースの役割を果たす。普通の関数の世界で定義した関数の戻り値を利用する時、return 関数によってモナドの値を返すように記述することができる。

4.>>= 演算子の引数はモナドの関数で、モナド型の値はその関数の引数であるという関係がある。モナドで集合の要素の役割を果たすのはあくまでも関数だが、これらの関数は必ずモナド型の値を引数にし、モナド型の値を返さなければならない。

5.モナドを利用したプログラムは、それぞれのモナド内で完結した小宇宙を持つことになる。モナド内の bind 演算子によるプログラムの結果はモナドの世界の外に出ることはないのでプログラムのモジュール化が保証される。プログラマはモナド内でプログラムしたものが他の領域に干渉することを懸念せずにプログラムを進めていくことができる。

まとめると、モナドでプログラムをする理由は、プログラムのカプセル化であるということ。モナドの世界では、集合の要素に当たるものが関数であること、また、モナド内の関数が扱う値は必ずモナド型の値でなければならないこと、return 関数はモナドの世界と外部世界とのインターフェースであるということ、bind 演算子を用いる演算はモナドの世界から出ることはないのでプログラマはモナド間の干渉を気にしないでプログラムできるということ、また、bind 演算子には関数の合成以外の機能をもたせることができるということなどではないだろうか。

Haskell に関するブログを見ても、みんなモナドの取り扱いについは苦慮しているようだが、それぞれの解釈でプログラムはきちんと動いているようだ。知識として学ぶのは大変だが、使うのは簡単だという Haskell の大原則がここでも見られる。モナドなど理解できなくても使ったもの勝ちなのだ。
[PR]
by tnomura9 | 2009-08-28 07:09 | Haskell | Comments(0)

モナド

0と正の自然数からなる集合、[0, 1, 2, .. ] には2項演算 (+) があり次の二つの法則を満たしている。

1. 結合法則: (a + b) + c = a + (b + c)
2. 単位元の存在: 0 + a = a + 0 = a

このような集合をモノイドという。このようなモノイドでは、結合法則のおかげで、次のような計算も基本的な二項演算に式の変形をすることができる。

(a + b) + (c + d) = a + (b + (c + d))

また、こうやって得られた結果もやはり、モノイド集合の要素になる。(+) の演算はモノイドの集合内で完結している。

上のモノイドは数の集合についての話だが、これを、関数の集合に拡張したものだモナドだ。

集合X = [0, 1, 2, .. ]上の関数で戻り値としてXの要素をかえす関数 y = f(x), x ∈ X, y ∈ X を考えてみる。y = x + x とか、y = x * x とかいろいろ考えられるが、それらの関数をすべて集めた集合を考えることができる。[f(x), g(x), h(x), .. ] がそれらの関数の集合とすると、これらの関数の合成関数をつくる演算子 >>= は、関数を引数とする2項演算子だ。つまり、f(x) >>= g(x) -> h(x) となる。

演算子 >>= がモナドの演算子となるためには、この演算子が結合法則を満たさなければならない。つまり、

(f(x) >>= g(x)) >>= h(x) = f(x) >>= (g(x) >>= h(x))

がせいりつするように定義されていなければならない。また単位元の存在も必要だ。つまり、

1(x) >>= f(x) = f(x) >>= 1(x) = f(x)

上の単位元は、左単位元 1(x) >>= f(x) と右単位元 f(x) >>= 1(x) に分けることができる。

ところで、Haskell のモナドの三基本則の1は return が左単位元であることを言っており、2は return が右単位元であること、3は関数の合成規則である bind (>>=) が結合法則を満たしている事を示している。

1. (return x) >>= f == f x
2. m >>= return == m
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

こう考えると、Maybe などのモナド型のデータの集合を引数とする関数が >>= 演算子の引数であることも理解できる。たとえば上の原則の1の式は、(return >>= f) x = f x と言う風にも書くことが出きるので、return が 左単位元であることがわかりやすい。

このようにモナドの構造は、モノイドの構造と同値なので、モナドの振る舞いを、[0, 1, 2, .. ] と (+) 演算のふるまいになぞらえて考えることができる。

このように関数の集合をモナドとしてとらえることで、関数の結合の方法をモナド内に完結させることができる。Haskell のプログラムの中に、様々なモナドの世界をつくることによって、副作用のある関数を隔離したり、特定のデータを扱う処理をモナドとしてモジュール化したりすることが、できるようになる。また、モナドの演算子を定義すれば、モナド内の様々な処理をデータの中身を考えずに関数の演算子によるつなぎ合わせて処理することができる。

モナドを圏論の見かたで理解することはかなり垣根が高いので、自分なりの受け取りかたで使ってしまいがちになるが、本質を理解して使うとすっきりしたプログラムをかけるようになるのだろう。

管理人自身が圏論にはお手上げなので偉そうな事は言えないが、モナドのようなものがプログラム言語の仕様として採用されているところに、Haskell の奥深さがあるのだろう。とりつきやすさと、理解を拒否する深さとが両立しているところも魅力なのかもしれない。
[PR]
by tnomura9 | 2009-08-27 22:31 | Haskell | Comments(0)

モノイド

モナドというのがやはりよく分からないので、グーグルであちこち覗いていたら、モナドが分かるためにはモノイドが分からないといけないらしいと言う事が分かった。モノイドはWikipediaでは次のように解説してあった。

モノイドとは次のような集合 S をいう。
S 上に二項演算 · が定義されていて(すなわち、写像 · :S×S → S が存在して)、 次の二つの条件を満たす。

  1. (結合法則) 任意の a, b, c に対して (a · b ) · c = a · (b · c )
  2. (単位元の存在) ある e が存在して任意の a に対して e · a = a · e = a

ただし、a · b は · (a, b) を表す。

二項演算 · が条件の 1. を満たすとき、S は半群と呼ばれる。つまり、モノイドとは「半群であって単位元を持つもの」である。
また、二項演算 · が上のほかに、逆元の存在を満たすとき、S は群と呼ばれる。

これだけでは分かりにくいが、たとえば0を含む自然数の集合が加算という2項演算についてモノイドなのだそうだ。[0, 1, 2, ... ] という集合から適当に二つの数を取り出して足し合わせるとその答えはやはりこの集合の要素になる。例えば2と3を取り出して2+3をつくるとそれは5でやはりこの集合の要素になる。しかし、2と3をとりだしてタプル (2, 3) をつくってもこのタプルは自然数の集合の要素ではない。

さらに、(1+2)+3 = 6 で、1+(2+3) = 6 なので計算の順序を変えても同じ値になる。また、0はどの数に右から足してもひだりから足しても元の数と同じになる。つまり、0 + a = a + 0 = a となる。

したがって、集合 [0, 1, 2, .. ] がモノイドになるためには、演算 + の性質が大切なようだ。

ところで、Wikipedia の定義で (a · b ) · c = a · (b · c ) の a, b, c には自然数、ドットには加算を当てることができたが、これを抽象化して、a, b, c に関数、ドットに関数の合成をあてることもできそうだ。例えば、関数を f, g, h 関数の合成を . とおくと上の式は、(f . g) . h = f . (g . h) と表すことができる。これは、Haskell の >>= 演算子の使い方に似ている。つまり f , g が関数なら、f >>= g もまた、関数で、(f >>= g )>>= h と f >>= (g >>= h) は同じ結果をもたらす。モノイドと同じ構造を持ちながら、対象が関数で演算が関数の合成であるものがモナドだ。

つまり、モノイドが数の集合と(+)演算を対象にしていたのに対し、モナドは関数の集合と関数の合成を対象にしているのだ。言い換えると、モノイドの構造はモナドの構造と相同性があるのだ。モノイドで数値と(+)演算の関係として見ていたものを、モナドでは関数と関数を合成する演算子(>>=)の関係に置き換えて考えることができる。わかりにくいモナドの振る舞いを、もう少しわかりやすいモノイドというか0と正の自然数からなる集合と(+)演算の関係の類推で考えることができるということだ。
[PR]
by tnomura9 | 2009-08-27 05:57 | Haskell | Comments(0)

3の倍数と3のつく数

3の倍数と3のつく数を求めるプログラム。

プログラム名: three.hs
three xs = [x| x <- xs, or [mod3 x, num3 x]]

mod3 n | (n `mod` 3) == 0 = True
          | otherwise = False

num3 0 = False
num3 n | n `mod` 10 == 3 = True
          | otherwise = num3 (n `div` 10)

実行例
Main> three [1..50]
[3,6,9,12,13,15,18,21,23,24,27,30,31,32,33,34,35,36,37,38,39,42,43,
45,48]

プログラム1行めの集合(リスト)の内包的定義の | の右の定義部分では、集合(リスト)xs の指定の後で、要素 x の満たすべき条件をコンマで区切って並べることができる。

プログラム4行目と8行目のガードの otherwise だが、otherwise = True (つまり、Trueの別名)なので上のガードのパターンマッチが失敗した場合に最後に実行される定義を記述するときに使う。

Haskellの解説書が難しいのは、それが、プログラミングを学問として研究している人やプロのプログラマーによって書かれているからではないだろうか。そういう人たちの興味の対象は言語としての性能や厳密さや実装など、プログラム言語についての高度な内容だ。

しかし、趣味のプログラマの興味はいかに容易に自分のアイディアをプログラムの形に実現できるかということであって、難しい理論はできれば避けて通りたいのだ。Haskell によるプログラミングは、対象(例えば数遊びのような)を選ぶと手続き型のプログラムより直観的に理解できる性質がある。素人が理解しやすいような視点からの Haskell の解説書がでれば、Excell のようにプログラマ以外の領域にユーザが増えるのではないかと思う。

スローガンになってしまったが、Haskell は難しくない。難しいのは Haskell の解説の方なのだ。
[PR]
by tnomura9 | 2009-08-26 03:13 | Haskell | Comments(0)

平均 分散 標準偏差

基本統計量を計算する Haskell のプログラムを見つけられなかったので。

n xs = fromIntegral(length xs)
m xs = sum xs / n xs
ss xs = sum [(x - m xs)*(x - m xs)| x <- xs] / (n xs - 1)
stat xs = [n xs, sum xs, m xs, ss xs, sqrt $ ss xs]

実行例
Main> stat [1,2,3]
[3.0,6.0,2.0,1.0,1.0]

出力は、[標本数、総和、平均、分散、標準偏差]

[(x - m xs)*(x - m xs)| x <- xs] は見慣れない表記だが、リストを要素の集合と見なすと、集合の内包的定義とほぼ同じ意味になる。上の例で言うと、集合(リスト) xs の要素を取り出し、(x-m) * (x-m) を計算した要素を集めた集合(リスト)という意味になる。

<- という記号は∈を模したもの。

使い出のある表記法で、次のようなものは、集合(リスト) [1,2,3] と集合(リスト) [4,5,6] の要素のすべての組み合わせのタプルを要素とする集合(リスト)を作ってくれる。

Hugs> [(x,y)| x <- [1,2,3], y <- [4,5,6]]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
[PR]
by tnomura9 | 2009-08-25 07:12 | Haskell | Comments(0)

Haskell を何に使うか

Haskell は入出力関係のプログラミングがやや面倒だ。副作用のある入出力のプログラムを無理に関数型のプログラミング言語に取り入れようとしたために、プログラムがやや煩雑になっているような気がする。プログラムを実務に役立てようと思ってHaskellを勉強し始めた人が、これは役に立たないと判断しても無理はない。

しかし、Haskellの本領はデータの入出力ではなく、アルゴリズムをそのまま記述できると言うところにある。たとえば、'a', 'b', 'c' という3文字の順列はどういうものがあるのか知りたいとしよう。こういうときに、ファイルからの読み込みや、書き込みのプログラムは必要ではない。ただ、この3文字の配列を知りたいだけだからだ。そういうときに Haskell でプログラムすると次のようになる。

import List

permutation [] = [[]]
permutation xs = concat [map (x:) $ permutation (delete x xs) | x <- xs]

実行例
Main> permutation ['a', 'b', 'c']
["abc","acb","bac","bca","cab","cba"]

このプログラムには入出力のプログラムはまったく必要ない。ただ、3文字の配列がどうなるかを見てみたかっただけだからだ。また、このプログラムも自分で考える必要はなく、「Haskell 順列」でグーグル検索すればそう時間もかけずに探し当てることができる。

頻繁に入出力を要するプログラムは、Haskell ではなくて他の手続き型のプログラム言語で書いた方がストレスが少ないだろう。しかし、アイディアをちょっとパソコンで検証してみたいという使い方には Haskell は非常に便利だ。手続き型か関数型かという全か無かの発想ではなく、Haskell の特徴を生かすような学びかたをすれば、学習する労力とメリットのバランスが十分にとれるような気がする。

入出力についても慣れの問題で、関数がIOモナドを返すように注意してさえおけば、そう違和感なく手続き型のプログラムを組むことができる。入出力をあまり要しないプログラムでHaskellのプログラムの癖に慣れてから、入出力プログラムに取り組めばよい。

とにかく、Haskell は思っていたように難しくもなく、特殊な用途にしか使えないわけでもない。普通に使うことができ、かつ、ストレスの少ない汎用言語なのだ。
[PR]
by tnomura9 | 2009-08-23 23:54 | Haskell | Comments(0)

Prelude の標準関数 索引

A Tour of the Haskell Prelude の日本語抄訳

A: abs, all, and, any, atan
B: break
C: ceiling, chr, compare, concat, concatMap, const, cos
D: digitToInt, div, drop, dropWhile
E: elem, error, even, exp
F: filter, flip, floor, foldl, foldl1, foldr, foldr1, fromInt, fromInteger, fst
G: gcd
H: head
I: id, init, isAlpha, isDigit, isLower, isSpace, isUpper, iterate
L: last, lcm, length, lines, log
M: map, max, maximum, min, minimum, mod
N: not, notElem, null
O: odd, or, ord
P: pred, putStr, product
Q: quot
R: rem, repeat, replicate, reverse, round
S: show, sin, snd, sort, span, splitAt, sqrt, subtract, succ, sum
T: tail, take, takeWhile, tan, toLower, toUpper, truncate
U: undefined, unlines, until, unwords
W: words
Z: zip, zipWith
演算子: (!!), (.), (**), (^), (^^), (%), (*), (/), (+), (-), (:), (++), (/=), (==), (<), (<=), (>), (>=), (&&), (||)
[PR]
by tnomura9 | 2009-08-23 23:05 | Prelude | Comments(0)