Namaran

Code daily. Without assist.

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 は既に見た値を読み飛ばし続け、プログラムは何も出力しないまま終わらなくなります。