Namaran

Code daily. Without assist.

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乗に比例する時間がかかります。