Haskell で無限列 CLI を作る — 遅延評価と『自分自身を参照するリスト』、素数の篩・Hamming 数

Haskell の遅延評価で、古典的な 無限列（素数の篩・Hamming 数・フィボナッチ・カタラン…）を扱う CLI を書いた。見せ場は 2 つ: (1) 遅延評価 — 式は必要になるまで、必要な分だけしか評価されない。だから「無限リスト」を値として定義でき、primes 15 や fib nth 100 は必要な分だけを force する、(2) 自己参照 — リストの tail をそのリスト自身から計算する（fibs = 0:1:zipWith (+) fibs (tail fibs)）。正格言語なら即発散するが、遅延なら各要素は読まれる直前に生成されるので成立する。直近の Rust/Go/Zig/OCaml（すべて正格）に対し、遅延という軸を足す一手。

📦 GitHub: https://github.com/sen-ltd/lazy-streams-hs

なぜ遅延評価か

直近の案件はすべて正格（先行）評価だった——Rust・Go・Zig、そして OCaml も式を即座に評価する。Haskell は 遅延（lazy）: 式は値が必要になるまで評価されず、しかも必要な分までしか評価されない。これは「値とは何か」を変える。ここでは各列を、一度定義しただけの 完全な無限リスト として扱い、primes 15 や fib nth 100 はちょうどその分だけを force する。

$ stream primes 15
primes (first 15): 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

$ stream fib nth 100       # 無限リストの深部 — ここだけが force される
fib #100 = 218922995834555169026

自己参照: リストを自分自身から定義する

最も純粋な実演は「tail をそのリスト自身から計算するリスト」。正格言語では即発散するが、遅延では各要素が読み戻される直前に生成されるので動く:

-- 各フィボナッチ数は「今まさに定義しているリスト」から読んだ 2 要素の和
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- Hamming 数（素因数が 2,3,5 のみ）: 自身を 2・3・5 倍した列を
-- マージし重複を除いたもの
hamming :: [Integer]
hamming = 1 : merge (map (*2) hamming)
                    (merge (map (*3) hamming) (map (*5) hamming))

factorials = 1 : zipWith (*) factorials [1..] も同じ手筋。テストは各列を深部まで駆動し——fibs !! 100、1000 番目の素数、500 個の Hamming 数——Integer（任意精度）で厳密一致を確認し、Hamming 数が 5-smooth かつ狭義単調増加であること、篩の出力がすべて実際に素数であることも検査する。

篩も遅延で

素数は遅延の逐次篩: 先頭を出し、その倍数を tail から除いて篩い続ける——無限リスト上なので、どこで止めるかは消費量が決める:

primes :: [Integer]
primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

正格言語なら [2..] を作ろうとした時点でメモリを食い潰す。遅延だからこそ「無限を書いて有限だけ使う」が自然に書ける。

Haskell 0 依存

外部パッケージは使わず base のみ。ghc -O2 で単一バイナリにコンパイルし、cabal/stack も不要にした（ハンドメイド・低依存の方針は他案件と同じ）。Integer が任意精度なので factorial nth 25 = 620448401733239439360000 のような値も厳密に出る。

src/Streams.hs — 列: fibs, primes, hamming, catalans, factorials, …
app/Main.hs    — CLI: stream <name> <count> / stream <name> nth <k> / stream list
test/Spec.hs   — 既知プレフィックス・深部インデックス・不変条件・素数性・遅延性

まとめ

遅延評価は「無限を値として書き、必要な分だけ払う」を可能にする。その真髄が 自己参照する無限リスト——fibs・hamming・factorials——であり、素数の篩も同じ発想で書ける。言語は Haskell を選び、Rust/Go/Zig/OCaml の正格系列に 遅延 の軸を足した。

📦 GitHub: https://github.com/sen-ltd/lazy-streams-hs