2026-10-08
Dedup.hs
import qualified Data.Set as Set
dedup :: Ord a => [a] -> [a]
dedup = go Set.empty
where
go _ [] = []
go seen (x:xs)
| x `Set.member` seen = go seen xs
| otherwise = x : go (Set.insert x seen) xs
main :: IO ()
main = print (take 3 (dedup (cycle [3, 1, 3, 2 :: Int])))
これは何を出力するでしょうか?
Answer
[3,1,2] です。
go はリストを先頭から見ていき、seen にまだない値なら結果に出して seen に加え、あれば読み飛ばします。Set は「もう出したか」を調べるためだけに使っていて、結果に並ぶのはリストに現れた順の値です。Set の中身は小さい順に並びますが、それは出力の順序には関係しないので、[1,2,3] にはなりません。
cycle が作るのは 3, 1, 3, 2 を繰り返す無限リストです。それでも go は、まだない値を見つけると x : go ... を返し、残りの計算は必要になるまで行いません。take 3 が求めるのは先頭の3要素だけで、それは無限リストの最初の4要素 3, 1, 3, 2 を見た時点でそろいます。Set を作るために無限リストを最後まで読もうとして終わらない、ということにはなりません。
take 4 にすると話は変わります。4つ目の新しい値はいつまでも現れないので、go は既に見た値を読み飛ばし続け、プログラムは何も出力しないまま終わらなくなります。