top page > computer > haskell > web_lecture > for_programmer > inf_list.html
更新日:
文責: 重城良国

無限リスト

はじめに

「遅延評価」と「遅延データ構造」をひっくるめて「遅延性」と呼ぶ。「遅延データ構造」の代表として「遅延リスト」がある。遅延性のおかげで「まず無限の長さのリストを作成し...」というコーディングができる。

終了条件を分離

多くのコードで終了条件は非本質的だ。「小さいほうから100個の素数を求める」とき遅延性を利用しないコーディングだと「100個で終了」の部分は「素数を求める」というアルゴリズムとからみあい分離しがたい。無限リストを使うと「すべての素数のリストを作成しそこから100個とる」ことができる。本質的な部分(素数を求める)から非本質的な部分(小さい方から100個とる)を分けられる。

1番小さな因数

factor.hs

自然数の最小の因数を求めよう。素朴な実装だ。効率は良くない。2から順に割っていき余りが0になるものを探す。2以上の「すべての」整数を含む無限リストを作成する。

[2 ..]

数nを割った余りが0になるものだけを集める。

filter ((== 0) . (n `mod`)) [2 ..]

最小の因数なので1番先頭をとる。

head $ filter ((== 0) . (n `mod`)) [2 ..]

nが2未満のときの無限実行を避けるためにガードでふるいわける。

factor n
| n < 2 = 1
| otherwise = head $ filter ((== 0) . (n `mod`)) [2 ..]

% ghci factor.hs
*Main> factor 221
13
*Main> factor 100233223200127
9997777

ただしこれは「自明だが効率の悪い方法」となる。「自明だが効率の悪い方法」を「複雑だが効率の良い方法」に変換していくことを運算と呼ぶ。Haskellは運算にも向いている言語だ。

平方数のリスト

すべての平方数のリストを見てみよう。

squares.hs

squares :: [Integer]
squares = map (^ 2) [0 ..]

ghci squares.hs
*Main> take 13 squares
[0,1,4,9,16,25,36,49,64,81,100,121,144]

関数takeは指定した数だけリストから値をとりだす。無限リストの表示はtakeを使わないと無限実行となる。

課題

  1. すべての正の立方数(整数の3乗となる数)のリストcubesを作成せよ
  2. cubesの先頭20要素を表示せよ

「データ構造としてのリスト」へもどる 「モンテカルロ法の説明」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics