無限リスト

Haskellでは、以下のように無限リストを再帰的に定義することができます：

ones = 1:ones

上記からones は 1 に ones を前置したもので定義されていることがわかります。通常の命令型言語では、 ones がリストとして事前に定義されていない場合、この構文は受け入れられません。しかし、Haskellでは遅延評価されるため、 これは完全に問題ありません。無限リストに対して次のような操作を行うことができます：

head ones -- 1
take 5 ones -- [1,1,1,1,1]
take 5 (map (*2) ones) -- [2,2,2,2,2]

しかし、すべてのリスト関数が無限リストに適用できるわけではありません。例えば、次の操作は問題があります：

tail ones -- 無限に実行されます
count ones -- Err

リスト全体の評価を必要とする関数はエラーを引き起こすことがわかります。

使用例

無限リストはいつ使うのでしょうか？例えば、自然数、偶数、奇数、素数などの数列に対応する無限リストを定義するために使用できます：

-- 自然数
nat = asc 1
  where asc n = n : (asc $ n + 1)
 
-- 偶数
even = map (*2) nat
 
-- 奇数
odd = filter (\x -> mod x 2 == 0) nat

もっと複雑なルールを持つ数列、例えばフィボナッチ数列を生成する無限リストを作成することもできます：

f 0 = 0
f 1 = 1
f n = (f $ n - 1) + (f $ n - 2)
 
fibs = map f nat

しかし、無限リストをどのように定義するかについて注意が必要です。上記のフィボナッチ数列の定義は理想的ではありません。 なぜなら、各 n に対して n までのすべてのフィボナッチ数列を計算する必要があり、時間計算量が O(2^n) となるためです（非常に悪い）。 代わりに次のように定義するべきです：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

上記の定義では何が起こっているのでしょうか？zipWith 関数は二つのリストに対して演算子（この場合は +）を適用し、 それらを一つのリストに結合します。fibs の各要素と tail fibs（fibs の最初の要素 0 を除いたもの）を合計することで、 二つの前の数を続けて加算し、フィボナッチ数列の無限リストを効果的に作成できます。これは、次の数を計算するために前の二つの数 を追跡するため、より良い実装です。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #19 - Infinite Lists. YouTube.