2026-10-07
Register.hs
registerAll :: Ord a => [a] -> ([a], [a])
届いた順に並んだ申し込みのリストを受け取り、同じ値を二度受け付けないように振り分ける registerAll を書いてください。返すのは、受け付けた値と断った値をそれぞれ届いた順に並べた2つのリストの組です。初めて届いた値は受け付け、すでに受け付けた値と等しいものは断ります。空のリストなら、どちらも空のリストです。
入力例 1
registerAll [3, 1, 3, 2, 1]
出力例 1
([3,1,2],[3,1])
入力例 2
registerAll ([] :: [Int])
出力例 2
([],[])
入力例 3
registerAll "aaa"
出力例 3
("a","aa")
Reference
import qualified Data.Set as Set
registerAll :: Ord a => [a] -> ([a], [a])
registerAll = go Set.empty
where
go _ [] = ([], [])
go seen (x:xs)
| x `Set.member` seen = (ok, x : ng)
| otherwise = (x : ok, ng)
where (ok, ng) = go (Set.insert x seen) xs
参考実装は、受け付け済みの値を集合 seen に入れて持ち回ります。値 x が seen にあれば断った側に、なければ受け付けた側に足し、残りのリストは x を加えた seen で振り分けます。受け付け済みかどうかを決めるのは、それまでに届いた値だけなので、入力例1では2つ目の 3 と 1 が断られます。
集合に Data.Set を使うので、型には Eq ではなく Ord を求めています。Ord があれば1回の検索は要素数の対数の時間で済み、受け付け済みの値をリストに入れて elem で調べるよりも、申し込みが多いときに速くなります。
掲載したのは参考実装で、唯一の正解ではありません。foldl で2つのリストを逆順に積み、最後に reverse する書き方もあります。受け付けた側だけが欲しいなら Data.List の nub でも求まりますが、nub は全体で要素数の2乗の時間がかかり、断った値も返しません。