[解決済み] Haskellでelemを使わずにリストから重複を削除する

質問

リストから重複を削除する関数を定義しようとしています。今のところ、動作する実装があります。

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs)   | x `elem` xs   = rmdups xs
                | otherwise     = x : rmdups xs

しかし、私はこれを elem . この場合、どのような方法が最適でしょうか？

でなく、自作の関数を使って行いたいのですが。 nub または nubBy .

解決方法は？

がないと無理だと思います。 elem (または独自の再実装)。

しかし、あなたの実装には意味上の問題があります。要素が重複しているとき、あなたは 最後 があります。個人的には、最初の重複した項目を残し、残りを削除することを期待します。

*Main> rmdups "abacd"
"bacd"

解決策は、「見た」要素を状態変数として通すことです。

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = rdHelper []
    where rdHelper seen [] = seen
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs
              | otherwise = rdHelper (seen ++ [x]) xs

このように、モラルのある nub は標準ライブラリで実装されています（ソースを読む ここで ). の小さな違いは nub の実装は、それが確実に 非厳格 一方 removeDuplicates はストリクトである（リスト全体を消費して戻る）。

厳密性を気にしないのであれば、原始的な再帰は実はやり過ぎなのです。 removeDuplicates は、1行で実装できます。 foldl :

removeDuplicates2 = foldl (\seen x -> if x `elem` seen
                                      then seen
                                      else seen ++ [x]) []