刪除列表中的重複元素

Question

我在編寫一些代碼時遇到了一些問題，但無法找到該錯誤。編程語言在方案中，問題如下：

只留下不重複的元素。 （a b）

我寫了下面的代碼。

(define x '(a b a a a c c)) 
    (display x) 
    (define z '()) 
    (define (removeReps y) 
    (if (null? y) 
     '() 
     (if(= (car y) (removeReps (cdr y))) '() (append z (car y))))) 
    (removeReps x) 
    (display z) 

爲了充分披露，這是一項家庭作業，但我無法解決它。

謝謝。

Answer 1

該解決方案不是，即簡單，您必須跟蹤迭代時找到的前一個元素，並且還有一個標誌，告訴您前一個元素是否出現過多次。這裏是我的投籃，假設輸入列表非空（是微不足道的處理情況下，如果輸入列表是空的，作爲練習留給讀者）：

(define (removeReps lst) 
    ; we need some extra parameters, use a named let for iteration 
    (let loop ([lst (cdr lst)] ; list to process, assuming non-empty 
      [prev (car lst)] ; pick first as "previous" value 
      [first #t])  ; flag: is this the first element in sequence? 
    (cond ((null? lst)  ; if we reached the end of the list 
      (if first   ; edge case: handle last element 
       (list prev) ; if it was the first in sequence add it 
       '()))   ; otherwise skip it and end list 
      ; if current element equals previous element 
      ((equal? (car lst) prev) 
      ; skip it, advance recursion and update flag 
      (loop (cdr lst) prev #f)) 
      ; new element, if previous element had exactly one repetition 
      (first 
      ; add it to output, advance recursion, update prev and flag 
      (cons prev (loop (cdr lst) (car lst) #t))) 
      ; new element, if previous element had more than one repetition 
      (else 
      ; skip it, advance recursion, update prev and flag 
      (loop (cdr lst) (car lst) #t))))) 

UPDATE

我真的很喜歡@Haskell中的@acs的實現：更高層次，並利用現有的過程而不是顯式遞歸，它適用於空列表，並且轉換爲Scheme並不困難（但是在Scheme中比在Haskell中更詳細）。這裏有另外一個選擇，使用球拍和SRFI-1的span程序，看看@ chris的回答，看看它是如何工作的解釋：

(require srfi/1) ; import `span` 

(define (group lst) 
    (match lst 
    ['() '()] 
    [(cons x xs) 
    (let-values (((ys zs) (span (curry equal? x) xs))) 
     (cons (cons x ys) (group zs)))])) 

(define (removeReps lst) 
    (filter-map (lambda (x) (and (= (length x) 1) (first x))) 
       (group lst))) 

或者更便攜，而無需使用特定的球拍程序和特殊形式：

(require srfi/1) ; import `span` 

(define (group lst) 
    (if (null? lst) 
     '() 
     (let ((x (car lst)) 
      (xs (cdr lst))) 
     (let-values (((ys zs) (span (lambda (e) (equal? e x)) xs))) 
      (cons (cons x ys) 
       (group zs)))))) 

(define (removeReps lst) 
    (map car 
     (filter (lambda (x) (= (length x) 1)) 
       (group lst)))) 

讓我們測試了一些邊緣案件的程序 - 它按預期工作與任何上述實施方式的：

(removeReps '(a b a a a c c)) 
=> '(a b) 

(removeReps '(x a a x b b x c c x)) 
=> '(x x x x) 

(removeReps '(a a a)) 
=> '() 

(removeReps '(a b b c c)) 
=> '(a) 

(removeReps '(a a b b c c d)) 
=> '(d) 

Answer 2

另一種可能的解決方案是以下

import Data.List 

removeDups :: Eq a => [a] -> [a] 
removeDups = map head . filter ((== 1) . length) . group 

寫入Haskell和使用庫函數group，length，(==)，filter，head，和map。

由於上述可能不是過於可讀的，我將逐步定義分段

首先構成上述定義

1. 首先各個部件的文本描述組列表納入包含相同要素的子列表。
2. 對於其中的每一個，檢查它的長度是否正好爲1.如果是這樣保留，否則將其丟棄。
3. 從列表的結果列表（其中我們知道每個元素的長度恰好爲1），我們實際上只需要單個元素，它們對應於單個列表的元首。

現在有些代碼。只要它們相等就可以將列表中的元素組合在一起的函數可以定義如下（對不起，我使用Haskell語法，因爲我對方案不是很熟悉，但它應該很容易翻譯）：

group :: Eq a -> [a] -> [[a]] 
group []  = [] 
group (x:xs) = (x:ys) : group zs 
    where (ys, zs) = span (== x) xs 

其中span是另一個庫函數，給定一些謂詞p，分割其輸入列表轉換元件的初始段所有滿足p和列表的其餘部分。爲了完整起見，可以把它定義如下

span :: (a -> Bool) -> [a] -> ([a], [a]) 
span _ [] = ([], []) 
span p xs@(x:xs') 
    | p x = let (ys, zs) = span p xs' in (x:ys, zs) 
    | otherwise = ([], xs) 

map，filter和head們更是標準的，那這些，我敢肯定他們的方案庫的一部分（如可能是group）。

我想我的主要觀點是，一旦將問題分解爲小塊的子問題（使用某些預定義的函數）併合並結果，解決方案很容易。

Answer 3

似乎處理測試用例的另一個遞歸解決方案。

;rep is the last repeated elem, input is the input list and first is boolean 
(define notrepeatedrec 
    (lambda (rep input first) 
    (cond ((null? input) (if (eq? first #t) (list rep) '())) 
      ((eq? rep (car input)) (notrepeatedrec (car input) (cdr input) #f)) 
      (else (if (eq? first #t) 
        (cons rep (notrepeatedrec (car input) (cdr input) #t)) 
        (notrepeatedrec (car input) (cdr input) #t)))))) 

;helper function to start the recursion 
(define notrepeated 
    (lambda (lst) 
    (notrepeatedrec '() lst #f))) 

Answer 4

在Common Lisp的，我會用棧的API列表：

(defun elim-dup (l) 
    (if (null l) 
     nil 
     (progn 
      (setf new()) 
      (dolist (x l) 
       (setq elem (pop l)) 
       (if (not (member elem new)) 
        (push elem new))) 
      new))) 

如果按照原來的順序喜歡，添加：

(reverse new) 

爲了避免原始列表的破壞，你必須取第n個元素而不是pop（並保持一個計數器）。流行更直接但破壞性強。

Answer 5

東西大致如下可能是可以接受的：

;; expr list -> list 
;; produce a list where leading elements equal to EXPR have been dropped 
(define (drop-in-front elt list) 
    (cond [(null? list) list]       ; empty list, we're done 
     [(equal? elt (first list))      ; first element matches 
     (drop-in-front elt (rest list))]    ; drop and repeat 
     [#t list]))         ; no match, we're done 

;; list -> list 
;; produce a list where blocks of repeated elements have been dropped 
(define (remove-repeated list) 
    (cond [(or (null? list)        ; empty list 
      (null? (cdr list)))      ; or list with one element 
     list]           ; we're done 
     [(equal? (first list)     
       (second list))      ; two matching elements in front 
     (remove-repeated        ; continue with 
      (drop-in-front (first list)     ; list where block in front 
         (rest list)))]    ; has been dropped 
     [#t           ; first elt different from snd 
     (cons (first list)       ; stick it in front of 
       (remove-repeated (rest list)))]))  ; cleaned up rest of list 

我真誠地希望你當然會很快出現一些風格指南。

如果您有機會，請嘗試查看Introduction to Systematic Program Design的講座或看看How to Design Programs。