2011-12-05 37 views
5

Ho scritto questo codice per creare un elenco dal en numero di argomenti datoSchema: Rimuovere i numeri duplicati dalla lista

(define (create-list . e) 
    e) 

Ma ho bisogno di rimuovere tutti i numeri duplicati dalla lista all'interno di questo blocco stesso.

Ho provato e cercato per ore e non riesco a trovare una soluzione senza posizionare dozzine di righe di codice su altri blocchi.

Per esempio diciamo che il mio ingresso è

(create-list . 2 2 3 5 5) 

mi serve l'elenco creato per essere '(2 3 5) e non' (2 2 3 5 5) ...

L'ordine dei numeri non importa.

+0

Vedi anche http://stackoverflow.com/a/8651932/450148 –

risposta

4

Fondamentalmente, è necessario fare qualcosa di simile:

(define (create-list . e) (dedupe e)) 

posso pensare a un modo molto semplice, ma probabilmente inefficiente per fare questo:

(define (dedupe e) 
    (if (null? e) '() 
     (cons (car e) (dedupe (filter (lambda (x) (not (equal? x (car e)))) 
            (cdr e)))))) 

Se non è possibile utilizzare le funzioni esistenti come filter, puoi crearne uno tu stesso:

(define (my-filter pred ls) 
    (cond ((null? ls) '()) 
     ((pred (car ls)) (cons (car ls) (my-filter pred (cdr ls)))) 
     (else (my-filter pred (cdr ls))))) 
+0

sarebbe possibile creare lo stesso codice con CDR/auto/CONS e solo procedure primitivi? (Nessun filtro/testa/coda) – spacing

+0

Sì. In effetti, 'head' e' tail' sono già solo 'car' e' cdr' rispettivamente (troppo Haskell nella mia mente). –

+0

Inoltre, si noti che la mia sintassi può essere un po 'off - ho usato Haskell solo di recente e ho sempre usato stk, che è un interprete di schemi obsoleto. –

0

Il più efficiente (trave rsing the list once) modo per fare ciò è definire una funzione che passa attraverso la lista elemento per elemento. La funzione memorizza un elenco di quali elementi sono già presenti nella lista dei duplicati.

Un vantaggio di questa soluzione rispetto a @Tikhon Jelvis è che gli elementi dell'elenco non devono essere in ordine, per essere deduplicati.

Data una funzione elem, che dice che se a è un elemento di l:

(define (elem? a l) 
     (cond ((null? l) #f) 
      ((equal? a (car l)) #t) 
      (else (elem? a (cdr l))))) 

Siamo in grado di attraversare la lista, la memorizzazione di ogni elemento che non abbiamo mai visto prima:

(define (de_dupe l_remaining already_contains) 
    (cond ((null? l_remaining) already_contains) 
     ((elem? (car l_remaining) already_contains) (de_dupe (cdr l_remaining) already_contains)) 
     (else (de_dupe (cdr l_remaining) (cons (car l_remaining) already_contains))))) 

Nota : per efficienza, restituisce gli elementi nell'ordine inverso

+1

La mia versione ha bisogno degli elementi in qualsiasi ordine? Per quanto ne so, non lo è. –

+0

@Tikhon Jelvis: Sembrava così; Non riesco a farlo restituire i valori corretti, però. Esempio: "(create-list 3 5 4 3 4 6)" restituisce "(3 3)" – amindfv

+0

Ciò non era dovuto all'ordine, ma perché ho ignorato accidentalmente un non nel predicato del filtro. L'ho risolto ora. –

2

Questo è più veloce:

(define (remove-duplicates l) 
    (cond ((null? l) 
     '()) 
     ((member (car l) (cdr l)) 
     (remove-duplicates (cdr l))) 
     (else 
     (cons (car l) (remove-duplicates (cdr l)))))) 

Ma ancora meglio, lo schema fornisce i duplicati di eliminazione, che fa esattamente ciò che si desidera.

0
(define (delete x) 
(cond 
((null? x) x) 
((= (length x) 1) x) | ((null? (cdr x)) x) 
((= (car x) (cadr x)) (delete (cdr x))) 
(#t (cons (car x) (delete (cdr x)))) 
) 
)