2026-09-13
Evens.hs
evens :: [Int] -> [Int]
evens = go []
where
go acc [] = reverse acc
go acc (x:xs)
| even x = go (x : acc) xs
| otherwise = go acc xs
print (evens [1 .. 10])は[2,4,6,8,10]を出力しますが、print (take 3 (evens [1 ..]))は何も出力しないままメモリを食い続けます。何が問題で、どう直せばよいでしょうか?
Answer
アキュムレータ付きの末尾再帰は、入力の[]に到達してreverse accを返すまで、結果のリストを1要素も渡せません。take 3が最初の要素を要求しても、goは無限リストを最後まで読もうとしてaccを伸ばし続けるだけです。正格評価の言語ではアキュムレータ付きの末尾再帰が定番の形ですが、遅延評価のHaskellでリストを作るなら、見つけた要素を:で先に返し、残りの再帰はその後ろに置く形(ガード付き再帰)にします:
evens :: [Int] -> [Int]
evens [] = []
evens (x:xs)
| even x = x : evens xs
| otherwise = evens xs
x : evens xsは、evens xsを評価する前に「先頭はx」という答えを返せるので、take 3は必要な3個を受け取った時点で残りを評価せずに終われます。アキュムレータもreverseも不要になり、有限のリストでも同じ結果です(標準のfilter evenもこの形で定義されています)。