Haskellの技法：無限リストのトリック

　Haskellは遅延評価システムを採用しており、コンパイラは実際に利用される式だけにメモリを割り当てるため、いくらでも式を定義することが可能である。この記事では、簡単な無限長のリストをさまざまな方法で扱い、このアプローチの有効な利用方法をお見せしよう。

　無限リストは、新しいプログラミングの世界を開いてくれる。無限リストを用いることで、手作業で作成せずともルールを与えるだけでシーケンスを生成することが可能になるのだ。これによって、コードが単純になることも多い。データ型は遅延評価され、かつ自己参照もサポートしているため、後続のリストを関数として定義することにより動的にリストを作成することができるのである。

この最も単純な例は、自然数のシーケンス（つまり、[1,2,3,4,..]）だろう。Haskellでは、次に挙げるようないくつかの表現方法がある。

numbers1 = 1 : map (+1) numbers1
numbers2 = 1 : [x+1 | x <- numbers2]
numbers3 = [1..]

$ ghci
*Main> take 10 numbers1
[1,2,3,4,5,6,7,8,9,10]
*Main> take 10 numbers2
[1,2,3,4,5,6,7,8,9,10]
*Main> take 10 numbers3
[1,2,3,4,5,6,7,8,9,10]

ここで、3つ目の手法が最も単純なのは明らかであろう。この表現方法は、一次のシーケンスを定義するために用いられる一般的な簡略化記法で、他の言語の範囲関数と同じような意味である。この記法は、一定の値ずつ増加または減少するシーケンスを生成するために、次のように利用することも可能である。

*Main> [1..10]
[1,2,3,4,5,6,7,8,9,10]
*Main> [1,3..10]
[1,3,5,7,9]
*Main> [10..1]
[]
*Main> [10,9..1]
[10,9,8,7,6,5,4,3,2,1]
*Main> take 20 [10,9..]
[10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9]

では、number1とnumber2のリストについて次に考えてみる。これらのリストで重要なのは、リストを作る際に自分自身を参照しているということである。これらのリストには終わりがないが、プログラムの動作時点でリストの最新の値を用いることによって、リストの個々の要素を作成することが可能なのだ。これはリストの内包記法と同様、map関数のようにリストを生成する関数を用いても同じように動作する。リスト内の要素は必要になったときに初めて作成され、リストの手前の要素ももし必要ならば同時に生成される。従って、潜在的には無限長のシーケンスであっても、無限のメモリを必要とすることはないのである。

より複雑な例として、階乗のシーケンスと三角数を考えてみよう。以下では、自己参照を持つリストの内包記法を用いた例と、組み込みのscanl関数を用いた例をお見せする（ghciでは、リストの内包記法の例を実行するために-fglasgow-extsコマンドラインオプションが必要となる）。