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つだけ残ります。