CODEWITHSUNDEEP
schemeracket
J-Y
J-Y

Reputation: 375

How to get rid of duplicates in a list, but keep the order

I am using Intermediate Student with Lambda in DrRacket, I was wondering how one would remove the duplicates in a list, while keeping the order. For example (remove-dup (list 2 5 4 5 1 2)) would produce (list 2 5 4 1). So far, I have this:

(define (remove-duplicates lst)
  (cond
    [(empty? lst) empty]
    [(member? (first lst) (rest lst)) 
     (remove-duplicates (rest lst))]
    [else (cons (first lst) (remove-duplicates (rest lst)))]))

, but there's a problem since it doesn't keep the order. Can someone point me in the right direction? Thanks for your time.

Upvotes: 8

Views: 30502

Answers (8)

Alexandre Araujo Moreira
Alexandre Araujo Moreira

Reputation: 487

I'm not sure if this is homework, but in case it is I'll post just the idea. If it's not tell me and I can put a solution here.

What you need is to keep track of the unique items you find, you can do that by using an auxiliary list, like an accumulator, to keep track of the ones you found so far.

Whenever you look at another item check to see if it's in the auxiliary list. In case it's not add it to the auxiliary list.

You'll end up with a reverse order of what you're trying to find, so you can just (reverse ...) it and you'll have your answer.

Upvotes: 0

No_name
No_name

Reputation: 2810

Old question, but this is an implementation of J-Y's idea.

(define (dup-rem lst)
  (cond
    [(empty? lst) empty]
    [else (cons (first lst) (dup-rem (filter (lambda (x) (not (equal? (first lst) x))) lst)))]))

Upvotes: 1

Salem Talha
Salem Talha

Reputation: 51

This is the solution:

(define (remove-duplicates lon)
  (foldr (lambda (x y) (cons x (filter (lambda (z) (not (= x z))) y))) empty lon))

Upvotes: 5

michael
michael

Reputation: 51

hmm i just had a racket exam recently, :/

the 'standard' remove-duplicates works fine but i was using pretty-big in drRacket so it had to be loaded using (require racket/list)

here is an alternative way :)

using mutation (not really in the spirit of racket but.. it works.)

    (define (set l)
        (define the-set '())
            (begin (for-each
                       (lambda (x)
                            (if (member x the-set)
                                #t
                            (set! the-set (cons x the-set))))
                       l)
                   (reverse the-set)))

hope this helps... cheers!

Upvotes: 0

danielrsmith
danielrsmith

Reputation: 4060

What you need to do is compare in reverse order the entire time. You can use the reverse function which returns a list in reverse order. That way you are always removing the 2nd+ occurrence of an element and not the first. Here is an example, however it is using let and if and not a cond expression.

http://www.cs.bgu.ac.il/~elhadad/scheme/duplicates.html

Good luck with your homework :)

Upvotes: 0

Eli Barzilay
Eli Barzilay

Reputation: 29546

If your goal is to get the functionality working, and not some homework question, then you don't need to do anything, just use remove-duplicates:

Welcome to Racket v5.2.
-> (remove-duplicates (list 2 5 4 5 1 2))
'(2 5 4 1)

Upvotes: 14

user448810
user448810

Reputation: 17876

Run through the list sequentially, inserting each element in a hash table or other dictionary. If you try to insert an element that is already in the hash table, do not add it to the outgoing list.

Upvotes: 0

Hans Nowak
Hans Nowak

Reputation: 7897

SRFI-1 has delete-duplicates, although it's inefficient. (I am not too familiar with Racket, but surely it has SRFI-1, and the source...)

http://srfi.schemers.org/srfi-1/srfi-1.html#delete-duplicates

Upvotes: 0

Related Questions