Namaran

Code daily. Without assist.

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乗の時間がかかり、断った値も返しません。