2026-10-08
Tags.hs
import qualified Data.Set as Set
uniqueTags :: [String] -> [String]
uniqueTags = Set.toList . Set.fromList
main :: IO ()
main = putStrLn (unwords (uniqueTags ["rust", "c", "rust", "haskell", "c"]))
uniqueTags は、タグの一覧から重複を取り除き、最初に現れた順に並べて返すつもりの関数です。main は ["rust", "c", "rust", "haskell", "c"] を渡し、結果を空白区切りで出力します。引数も標準入力も使いません。いまは c haskell rust が出ますが、本来は rust c haskell が出るはずです。
Answer
Wrong
uniqueTags = Set.toList . Set.fromList
Set.fromList で重複は消えますが、Set は要素を Ord の順に並べて持つので、どの要素が先に入ったかは残りません。Set.toList はその中身を小さい順に返すため、文字列の辞書順の c haskell rust になります。
Right
uniqueTags = go Set.empty
where
go _ [] = []
go seen (t:ts)
| Set.member t seen = go seen ts
| otherwise = t : go (Set.insert t seen) ts
並び順はリストの側で保ち、Set には出したタグを覚えさせるだけにします。go はリストを先頭から見て、seen にまだないタグだけを結果に出すので、rust、c、haskell の順に残ります1。
Data.Listのnubも、最初に現れた順を保って重複を取り除きます。ただし出したタグすべてと==で1つずつ比べるので、タグの数の2乗に比例する時間がかかります。Setを使うと、確認1回あたりの時間はSetの大きさの対数に比例する程度で済みます。