無限リストの基礎の基礎

Haskellでは、次のような、無限の長さのリストを簡単に定義できます!!

ones = 1:ones

とっても気持ち悪い定義ですね。onesはどのように評価されていくのでしょうか。

ones 
---ones=1:onesで書き換える。
~> 1:ones
---やはりones=1:onesで書き換える。
~> 1: (1: ones)
---同上
~> 1:(1:(1:ones))
---以下同様
~> 1:1:1:1:1:.....

ということで、onesは、1が無限に続くリストになることがわかりますね。

しかし、無限の長さのリストなんて定義できても、どのように使えばいいのでしょうか。実際に無限リストの値を使う場合には、有限の部分だけ使うことになります。

ones = 1:ones

main = do
    print $ take 10 ones

実行結果

[1,1,1,1,1,1,1,1,1,1,]

あらかじめ無限の長さでとして定義しておけば、使いたいときに使いたい長さ分だけ使える、というところが、無限リストのメリットですね。

無限リストで等差数列、等比数列、無限級数

もうちょっと役に立ちそうな例として、高校数学でもお馴染みの等差数列と等比数列を Haskellで定義してみたいと思います。

便利なiterateという関数があるお陰で、簡単なんですけどね。

iterate f x ~> [x, f x, f (f x), f (f (f x)), .....,  ]

ということで、初項1, 公比2の数列

[1, 2, 4, 8, 16, 32, ....]

という数列であれば、以下のように定義できます

iterate (*2) 1

だから、一般的な等差数列、等比数列も簡単なのがわかりますね。

arith_seq a d = iterate (+d) a
geo_seq a r = iterate (*r) a

無限級数も、scanlという関数のお陰で簡単です。

series seq = scanl (+) 0 seq

では、数列

[1, 1/2, 1/4, 1/8, 1/16, ...]

の和が、2に収束するということを確かめてみましょう。

p e = (\x -> (2-x) >= e)
l = series (geo_seq 1 0.5)

takeWhile (p 0.001) l

[0.0,
1.0,
1.5,
1.75,
1.875,
1.9375,
1.96875,
1.984375,
1.9921875,
1.99609375,
1.998046875]

有理数 p / qの小数表示に対応する無限リストはこんな感じ。

rat p q = (p `div` q) : rat ((p `mod` q) * 10) q