Namaran

Code daily. Without assist.

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。

  1. Data.List の nub も、最初に現れた順を保って重複を取り除きます。ただし出したタグすべてと == で1つずつ比べるので、タグの数の2乗に比例する時間がかかります。Set を使うと、確認1回あたりの時間は Set の大きさの対数に比例する程度で済みます。