Namaran

Code daily. Without assist.

2026-10-30

SortedSet.hs

insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x ys@(y : rest)
  | x < y = x : ys
  | x == y = rest
  | otherwise = y : insert x rest

main :: IO ()
main = print (foldr insert [] [2, 3, 1, 3, 2, 2])

insert は、重複の無い昇順のリストに x を入れて、昇順で重複の無いリストを返すつもりの関数です。x がすでにリストにあれば、リストをそのまま返します。main は [2, 3, 1, 3, 2, 2] の値を空リストに順に入れるので、本来は [1,2,3] と出力されるはずが、いまは [1,2] と出力されます。

Answer

Wrong

| x == y = rest

ys@(y : rest) の rest は y より後ろだけのリストです。x == y のときに rest を返すと、そのままにするはずの y が落ち、すでにある値を入れることが、その値を消すことになります。値は入れるたびに、無ければ入り、あれば消えるので、入れた回数が奇数の値だけが残ります。

main の入力では、3は2回なので入ってから消え、1は1回なので残ります。2は3回なので、入って、消えて、また入ります。重なった値がすべて消えると考えると [1] になりますが、実際には2が残って [1,2] になります。foldr は右の要素から順に入れますが、どの値が残るかは回数だけで決まるので、入れる順は結果を変えません。

Right

| x == y = ys

ys は as パターンで付けた、y を含む受け取ったリスト全体の名前です。x がすでにあるときは ys を返せば、リストは1要素も変わらず、同じ値を何度入れても1つだけ残ります。