2026-10-08
KeepLast.hs
keepLast :: Ord a => [a] -> [a]
リストから重複を取り除き、同じ値のうち最後に現れたものだけを残す keepLast を書いてください。残った要素は元のリストでの位置の順に並べます。空のリストには空のリストを返します。
入力例 1
keepLast [1,2,1,3,2]
出力例 1
[1,3,2]
入力例 2
keepLast "banana"
出力例 2
"bna"
入力例 3
keepLast []
出力例 3
[]
Reference
import qualified Data.Set as Set
keepLast :: Ord a => [a] -> [a]
keepLast = reverse . go Set.empty . reverse
where
go _ [] = []
go seen (x:xs)
| Set.member x seen = go seen xs
| otherwise = x : go (Set.insert x seen) xs
参考実装の go は、先に現れたものを残す重複除去です。seen に出した値を覚えておき、2回目以降に現れた値を読み飛ばします。Set を使うので、値ごとの確認は Set の大きさの対数に比例する時間で済みます。
最後に現れたものを残すには、リストを裏返してから go に渡します。裏返したリストでは、元のリストで最後に現れたものが最初に来るので、go が残すのはちょうどそれです。入力例1の [1,2,1,3,2] は [2,3,1,2,1] になり、go は [2,3,1] を返します。これをもう一度裏返すと、元の位置の順の [1,3,2] に戻ります。最後の reverse を忘れると、並び順が逆になります。
掲載したのは参考実装で、唯一の正解ではありません。foldr でリストの右から Set を育てながら結果を組み立てても、裏返しを使わずに書けます。Data.List の nub を裏返しと組み合わせても同じ結果になりますが、nub は出した値すべてと1つずつ比べるので、長いリストでは要素数の2乗に比例する時間がかかります。