人気ブログランキング | 話題のタグを見る

Haskell あれこれ 無限リストとモジュール化

Haskell の解説をネットで探すと高級で難しい内容のものが多い。

なるほど、すごいことができるのだと感心するが、自分とはあまり関係ないとあきらめてしまう結果となってしまう。このブログでは、逆に、Haskell を知識や経験の少ないホビーストがどうやって楽しむことができるかということに焦点を当てていきたい。

知識はなくても、Haskell をいじるのは楽しいのだ。

ということで、Haskell にあって、他の言語にはない「無限リスト」の話。「無限リスト」とは要素の配列が無限に続くリストのことだ。Hskell で [1..10] は1から10までの整数のリストを作る。

Hugs> [1..10]
[1,2,3,4,5,6,7,8,9,10]

しかし、[1..] は無限に続く数値のリストを作り出す。したがって、WinHugsの場合 Actions - Stop メニューを選択しないと止まってくれない。(Linux の場合は Ctrl + c を入力する。)

Hugs> [1..]
[1,2,3, ...

無限リストなんか何の役に立つのだろうと思うが、take 関数で無限リストの初めの何個かを切り取ることができる。

Hugs> take 10 [1..]
[1,2,3,4,5,6,7,8,9,10]

つまり、take 10 という関数で、無限リスト [1..] の初めの10個を切り取ることができて、暴走もしない。このやり方で重要なのは、take 10 というコントロールの部分と、[1..] という無限リストの部分が完全に独立している(モジュール化している)ということだ。したがって、take 10 という操作は [1..] だけでなく、どんな無限リストにも適用できる。たとえば [2,4..] というのは偶数列の無限リストだが、これに、take 10 を適用して次のように初めの10個の偶数のリストを取り出すことができる。

Hugs> take 10 [2,4..]
[2,4,6,8,10,12,14,16,18,20]

フィボナッチ数のようなものも無限リストで定義しておくと、やはり take 10 を使うことができる。

Hugs> take 10 fib where fib = 0:1:zipWith (+) fib (tail fib)
[0,1,1,2,3,5,8,13,21,34]

無限リストに適用できるのは take 関数だけではない、n 番目の要素を取り出す !! を使うと無限リストから n 番目の要素(スタートは0番目から) を取り出すことができる。

Hugs> [1..] !! 2
3
Hugs> [2,4..] !! 2
6

フィボナッチ数の場合も同じことができるが、ファイルにフィボナッチ数を発生する関数を作成して :load しなければならない。

Hugs> :e fib.hs

エディターが起動したら次のスクリプトを作成する。

fib :: [Integer]
fib = 0:1:zipWith (+) fib (tail fib)

スクリプトを作成したら、エディターを閉じて、:load コマンドでロードすると、fib 関数が使えるようになっている。

Main> :l fib.hs
Main> take 10 fib
[0,1,1,2,3,5,8,13,21,34]
Main> fib !! 2
1

重要なのは、無限リストが使えると、リストのデータと、それをコントロールする take, !! などの操作を完全に分けることができるということだ。ところが、手続き型のデータでは、上のような操作はデータを発生するプログラムと一緒になっており、データの種類ごとにプログラムしなおさなければならない。

これに対し、Haskell では、無限リスト [1..] にも、[2,4..] にも、fib にも同一の take や !! 等の関数を使うことができる。したがって、プログラムする側は無限リストさえ作成すれば後は、[1..] の時と同じ発想で無限リストを操作できる。無限リストを操作できる関数にはこのほかにも drop, takeWhile, dropWhile, zip などがあるが、これらの関数も一回覚えるといろいろな無限リストに適用できるので覚える手間が一回で済む。

次のプログラムは素数の無限リストを発生するプログラムだが、

primes :: [Integer]
primes = sieve [2..]

sieve :: [Integer] -> [Integer]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

これも全く同じように、take や !! でコントロールすることができる。

Hugs> :e pirmes.hs
Main> :l primes.hs
Main> take 10 primes
[2,3,5,7,11,13,17,19,23,29]
Main> primes !! 3
7

Haskell の面白さは、このように関数がモジュール化されているために、同じ操作が様々なデータに同じように適用できるため、余計なことを考えなくて良い気軽さを味わえることだ。大して難しいことはできなくても、自分で発想したとおりに(プログラム言語によるアルゴリズムにあまり翻訳しなくても)プログラムを書いてそれが動くという体験をするのは何とも言えない楽しさがある。
by tnomura9 | 2009-08-17 23:47 | Haskell | Comments(0)
<< Haskell 記事リスト Haskell あれこれ。fo... >>