CODEWITHSUNDEEP
listrecursionduplicatesschemeworkflow
user1252121
user1252121

Reputation: 41

Scheme function that checks a list for duplicates

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?

Upvotes: 4

Views: 9055

Answers (5)

bmc
bmc

Reputation: 857

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

Upvotes: 0

JennyToy
JennyToy

Reputation: 628

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

Upvotes: 3

gcbenison
gcbenison

Reputation: 11963

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.

Upvotes: 1

Óscar López
Óscar López

Reputation: 235984

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:

  1. What happens if the list is empty? that means that there aren't any duplicates in it
  2. 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)
  3. 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

Upvotes: 1

soegaard
soegaard

Reputation: 31147

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

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

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

Upvotes: 0

Related Questions