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

Question

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.

Solution 1

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)

Solution 2

This is the solution:

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

Solution 3

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)))]))

Comments

[J-Y]

I took a look at the website, but I believe the source code provided does not work in Racket.

[Sam Tobin-Hochstadt]

You can use srfi/1 in Racket by just adding (require srfi/1) to your program. However, remove-duplicates as mentioned in the first answer is even easier to get -- it's there by default in Racket.

[Giacomo Pigani]

I have racket 6.0.1 but it tells me the function isn't defined

[Eli Barzilay]

You need to use the regular language, not the student languages.

[Thumbnail]

You'd better prefer a hash set to a list to keep the items you've seen. With a list, the function is Theta (n^2) . With a hash-set, it's Theta (n).