Scheme function that checks a list for duplicates

Question

I need to write a Scheme function that checks a list for duplicate entries. I think I've got the workflow down on paper, I just need help getting it from the paper into code.

First I need to check if it's an empty list. So I've got...

(define (checkDupe mylist)
  (if (null? mylist)
      ()
      (checkDupeB mylist)
  )
)

Then I have this sort of "double recursion" where I check the first number against the rest of the list, then the second number against the rest of the list, and so on, and when it finds a match it spits out a #t, if it hits the end and doesn't find a match, the result of the function is #f. The problem is I just can't wrap my head around this recursion stuff. This is a homework question, but I'm geniunely interested in learning this stuff though.

Can someone throw some code at me and help me work through this?

You might want to take a look at the draft of How To Design Programs, 2nd edition, especially starting around chapter 4: http://www.ccs.neu.edu/home/matthias/HtDP2e/htdp2e-part2.html. That chapter covers how to methodically approach these kind of list problems. — dyoo, Mar 06 '12 at 18:04
to understand recursion you need only understand counting. we count with natural numbers. what is a natural number? it is either 0, or one more than a natural number. [imagine you're a wizard](http://stackoverflow.com/a/19951540/849891) in a middle of a hot arid desert. you know a direction to each city nearby; how do you decide were to go? you want to find the nearest one. how can you know a distance to a city without actually going there? you're a wizard; you create a copy of yourself, one step closer to that city, and ask *it* for the answer. Since he's a wizard too, he repeats the process. — Will Ness, Sep 11 '15 at 08:33

score 3 · Answer 1 · answered Sep 09 '15 at 19:17

3

Here it is one way

(define (has-duplicates? lst) 
  (cond
     [(empty? lst) #f] 
     [(not (not (member (first lst) (rest lst)))) #t]
     [else (has-duplicates? (rest lst)) ]))

answered Sep 09 '15 at 19:17

JennyToy

588
4
19

Óscar López · Answer 2 · 2012-03-06T21:00:05.803

I'm guessing this is homework. It's a simple procedure, but you're missing a case in your navigation flow, as three cases need to be considered:

What happens if the list is empty? that means that there aren't any duplicates in it
What happens if the current element of the list exists somewhere in the rest of the list? then it means that there's a duplicate in the list (hint: the member procedure might be useful)
If none of the above are true, continue with the next element

As further help, here's the general idea, fill-in the blanks:

(define (checkDupe mylist)
  (cond ((null? myList) ???) ; case 1
        (??? #t)             ; case 2
        (else ???)))         ; case 3

score 1 · Answer 3 · answered Mar 08 '12 at 01:46

Iterating through the entire list again for each member to check for duplicates can be expensive - O(n^2). Checking for adjacent duplicates is much cheaper -- O(n). If you don't mind changing the order of elements in the list, you can make all duplicates adjacent by sorting the list first. The list has to be composed of elements that can be compared by some > operator.

(define (remove-duplicates xs)
  (fold-right cons-if-not-duplicate '() (sort xs >)))

An advantage of this approach is that it relies on a standard fold operator rather than custom recursion. Since this is homework I'm leaving out a definition of cons-if-not-duplicate.

score 0 · Answer 4 · edited Oct 09 '15 at 03:05

0

This is my solution which, though untested should work,

(define rmdup
   (lambda list
      (cond
         ((null? list) '())
         ((eq? (car list) (car (cdr list)) (rmdup(cdr list)))
          (else( cons (car list) (rmdup(cdr list)))))))

Algorithm out loud: If the initial car equal to the next car? Chop initial and go again, or else, keep it, then proceed. This way we keep only unique copies, not anything with a neighbor sibling

edited Oct 09 '15 at 03:05

Foon

6,148
11
40
42

answered Oct 09 '15 at 02:56

bmc

817
1
12
23

I fixed your formatting, but I don't think this works. (Hint: what does (rmdup '(1 2 3 1)) return? – Foon Oct 09 '15 at 03:06

score 0 · Answer 5 · answered Mar 06 '12 at 14:47

There is more than one way to solve the problem. Here is suggestion.

write a helper function (is-element-in-list? x l), which returns true if x is in the list l and false otherwise.

Fill in the blanks in

(define (contains-duplicate? l)
   (cond [(list? l) (or <check whether (first l) is in (rest l)>
                        <check where (rest l) contains a duplicate> )
         [else false]))

Scheme function that checks a list for duplicates

5 Answers5