Schema function that checks the list of duplicates
I need to write a Scheme function that checks a list for duplicate entries. I think I have a paper workflow, I just need help getting it from paper to code.
First I need to check if it is empty. So, I have a...
(define (checkDupe mylist)
(if (null? mylist)
()
(checkDupeB mylist)
)
)
Then I have a "double recursion" like this where I check the first number against the rest of the list, then the second number against the rest of the list, etc., and when it finds a match it spits out a #t
if it hits the end and not finds matches, the result of the function is #f
. The problem is, I just can't get my head around this recursion. This is a homework related question, but I am genuinely interested in learning about this material.
Can someone throw me some code and help me deal with this?
source to share
I assume this is homework. This is a simple procedure, but there is no case in your navigation flow as there are three cases to consider:
- What happens if the list is empty? this means there are no duplicates in it.
- What happens if the current list item exists somewhere in the rest of the list? then it means there is a duplicate in the list (hint: procedure
member
might be helpful) - If none of the above is correct, go to the next item
As an additional help, here's a general idea, fill in the blanks:
(define (checkDupe mylist)
(cond ((null? myList) ???) ; case 1
(??? #t) ; case 2
(else ???))) ; case 3
source to share
Iterating through the entire list again for each member to check for duplicates can be costly - O (n ^ 2). Checking for adjacent duplicates is much cheaper - O (n). If you don't mind reordering the items in the list, you can make all duplicates contiguous by sorting the list first. The list should consist of items that can be compared using some> operator.
(define (remove-duplicates xs)
(fold-right cons-if-not-duplicate '() (sort xs >)))
The advantage of this approach is that it relies on the standard fold operator rather than regular recursion. Since this is homework, I leave the definition cons-if-not-duplicate
.
source to share
There are several ways to solve the problem. Here's a suggestion.
-
write a helper function (is-element-in-list? xl) that returns true if x is in 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]))
source to share
This is my solution which, although 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)))))))
Aloud algorithm: If the starting car is equal to the next car? Drop the initial one and go again, or save it, then continue. This way we only keep unique copies, not anything with the neighboring sibling
source to share