중복 제거하지만 순서 유지

Question

rmdup :: [Int] -> [Int] 
rmdup [] = [] 
rmdup (x:xs) | x `elem` xs = rmdup xs 
      | otherwise = x: rmdup xs 

위의 코드는 Integer 목록에서 중복을 제거하지만 첫 번째 항목은 제거하고 두 번째 항목은 제거합니다. 예를 들어 :

rmdup [1,2,3,1,4] 

가 발생합니다 :

[2,3,1,4] 

가 어떻게이 순서를 유지하고이 산출하기 위해 변경할 수 있습니다 : [1,2,3,4]를? 참고, 내장 함수를 사용하고 싶지 않습니다.

Answer 1

방법 다음은 어떻습니까? 이 두번 지정된 목록을 역방향 또한 미친 듯이 acC++ [x] 비효율적을 회피 : elem 이후

rmdup :: Eq a => [a] => [a] 
rmdup xs = rmdup' [] xs 
    where 
    rmdup' acc [] = [] 
    rmdup' acc (x:xs) 
     | x `elem` acc = rmdup' acc xs 
     | otherwise = x : rmdup' (x:acc) xs 

Answer 2

이전에 본 적이있는 요소를 나중에 무시한 다음 본 모습을 기록해야합니다 (예 : foldl 또는 foldl'). 당신이 원하는 것은 반대 순서로 입력 목록을 전달하고 계산이 완료되면 한 번 다시 그 결과를 반대하는 것입니다 달성하기

import Data.List (foldl') 

rmdup :: (Eq a) => [a] -> [a] 
rmdup = foldl' step [] 
    where step acc x 
      | x `elem` acc = acc 
      | otherwise = acc++[x] 

Answer 3

한 가지 방법은 다음과 같습니다

는 가능한 구현입니다. 그러나이 솔루션은 효율적이지 않습니다.

rmdup :: [Int] -> [Int] 
rmdup xs = reverse $ rmdup' (reverse xs) 
    where 
    rmdup' [] = [] 
    rmdup' (x:xs) | x `elem` xs = rmdup' xs 
        | otherwise = x: rmdup' xs 

데모 :

ghci> rmdup [1,2,3,1,4] 
[1,2,3,4] 

Answer 4

은 O (N)이며, 각 요소를 확인하는 데 사용하는 방법에 기초하여, 솔루션 (N은^2) O이다. 중복 문제에 대한 "표준"효율적인 솔루션은 중복을 확인하기 전에 목록을 정렬하는 것입니다. 여기서 우리는 요소를 보존 할 필요가 있으므로 좀 더주의해야합니다.

import Data.List 
import Data.Ord 

rmdupSorted :: Eq b => [(a,b)] -> [(a,b)] 
rmdupSorted (x@(_,xb):xs@((_,yb):_)) | xb == yb = rmdupSorted xs 
            | otherwise = x : rmdupSorted xs 
rmdupSorted xs = xs  -- 0 or 1 elements 

rmdup :: Ord a => [a] -> [a] 
rmdup = map snd . sort . rmdupSorted . sortBy (comparing snd) . zip [0..] 

main = print $ rmdup [1,2,3,4,5,4,6,1,7] 

sortBy 기능은 rmdup 함수가 어떤 요소의 모든 중복 항목을 제거하지만 마지막으로 발생하는 일에 대한 것입니다하는 안정적 종류이라고 가정. sortBy이 안정적이지 않으면 rmdup은 지정되지 않은 항목을 모두 제거합니다 (즉, rmdup [1,2,1]은 [2,1] 대신 [1,2]을 반환 할 수 있음).

복잡성은 이제 O (n log n)입니다.

이제 OP가 요청한대로 라이브러리 함수없이 위 코드를 다시 작성해야합니다. 나는 이것을 독자에게 연습으로 남겨 둘 것이다. :-P