• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 794
  • Last Modified:

Scheme recursion question

I need to write a function that leaves only the elements that are not repeated in string (a b a a a c c).

The result would be (a b).

I am new to Scheme and LISP so this is all very confusing to me, expecially recursion.

Any help is appreciated.
0
InfoTechEE
Asked:
InfoTechEE
  • 8
  • 5
  • 2
2 Solutions
 
InfoTechEEAuthor Commented:
Here's what I have so far. When the 1st and 2nd letters don't match, just print out the 1st letter. The part I'm struggline with is what do if there is a match between 1st and 2nd letters?

(define (remove-dups lst)
    (cond
      ((null? lst) '())
      ((null? (cdr lst)) (display(car lst)))
      ((equal? (car lst) (car(cdr lst))) --->  NOT SURE WHAT TO DO HERE   <-----)
      (else (display(car lst)) (remove-dups(cdr lst)))))
0
 
SuperdaveCommented:
I don't understand the example.  b is the only element that is not repeated.  (a c) are the elements that are repeated.  Do you need just the non-repeated ones, just one copy of the repeated ones, or just one copy of everything?

In any case, with Scheme, it's better to think in terms of the first element and the rest of the elements rather that the 1st and 2nd elements.  For example, to find unique elements, cons the first element with everything in the rest of the list except for the first element (but after first applying the function recursively on the rest of the list).
0
 
InfoTechEEAuthor Commented:
Sorry, I edited the orginal post. The results should be (a b).

I basically need to remove all consecutive duplicates.

0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
SuperdaveCommented:
Then I think the way you're doing it makes sense.  The NOT SURE WHAT TO DO could check the third element also.  If different, then do (remove-dups(cdr (cdr lst))) to ignore the first two elements; if the same, then do (remove-dups(cdr list)) to ignore the first element and you know at least the next two will be removed in the next recursion.
0
 
InfoTechEEAuthor Commented:
That approach would not work because comparing the 1st and 3rd elements in the string (a b a a a c c) would make them equal. Even though they are equal, they are not in consecuitve order.
0
 
TommySzalapskiCommented:
When you find a pair that is equal, do nothing. Just call the function to look at the next pair. Eventually they either will not equal or you will run to the end of the string. If you run to the end of the string, you will be comaring the character with a null string which is not equal so it will print and all will be well.
0
 
TommySzalapskiCommented:
So in the case of a b a a a c c, you actually print the first, secong, fifth, and seventh characters. You end up removing the first instances of the duplicated characters and just print the last one, but it works out the same. So in the NOT SURE WHAT TO DO HERE, just do (remove-dups(cdr lst))
0
 
InfoTechEEAuthor Commented:
Hi Tommy,

I need my final result to be (a b),
by leaving only the elements that are not consecutively repeated in the string (a b a a a c c).

You suggestion would result in (a b a c). I need (a b).
0
 
TommySzalapskiCommented:
Sorry. Didn't realize that this was different than the last one. If you still want only one fuction that takes only one string, it's going to be difficult.
I can think of one way to do it.
You need to look at three at a time.
If the first two don't match, print the first one, remove it, and call the function again.
If the first two match but don't match the third, remove both and call.
If all three match, remove one and call this way you can still tell it was a duplicate on the next call.
0
 
InfoTechEEAuthor Commented:
Here's what I have so far, I just need to know if there is an exit function, or more of a DO NOTHING function. Using DrRacket, and feeding the string '(a b a a a c c), produces the results (a b '() ), because I'm really not sure, how to simply QUIT and do nothing.

(define (remove-dups lst)
    (cond
      ((null? lst) '())
      ((null? (cdr lst)) (display(car lst)))
      ((null? (cdr(cdr lst))) (remove-dups-helper lst))
      ((not(equal? (car lst) (car(cdr lst)))) (display(car lst)) (remove-dups(cdr lst)))
      ((not(equal? (car lst) (car(cdr(cdr lst))))) (remove-dups(cdr(cdr lst))))
      ((equal? (car lst) (car(cdr(cdr lst)))) (remove-dups(cdr lst)))
      ))

(define (remove-dups-helper lst)
  (cond
    ((equal? (car lst) (car(cdr lst))) '())
    (else (display(car lst)) (display(car(cdr lst))))))
0
 
InfoTechEEAuthor Commented:
Nevermind, figured it out.
0
 
InfoTechEEAuthor Commented:
Thanks everyone. I have one other Scheme question that I posted below. Please take a look.

http://www.experts-exchange.com/Programming/Misc/Q_26971327.html

I'll be closing this question shortly.
0
 
TommySzalapskiCommented:
If you hit 'Ask a related question' then it will notify us so you don't need to post the link to the new question. Also, anyone who sees the new question can refer back to this one.
0
 
InfoTechEEAuthor Commented:
Where is that option?
0
 
TommySzalapskiCommented:
Oh yeah, it only pops up after you close the question. It's right by the window you type in. It says:
This question has already been closed and has had points assigned. Post additional comments only if you want to clarify or comment on the solution. You can also ask a related question.
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

  • 8
  • 5
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now