Solved

# Scheme Recursion question

Posted on 2011-04-19
685 Views
I need to write a function the removes the second and succeeding adjacent duplicates of string (a b a a a c c).

The result would be (a b a c).

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

Any help is appreciated.
0
Question by:InfoTechEE

LVL 37

Expert Comment

The recursion part is simple in this one. Just keep track of the last letter that you saw and use it to decide if you should print the next one. Then pass the new character and the rest of the string into the function again. So your function should take a 'lastChar' argument and a string and return a string.

Is this for homework, your personal learning, or a work project so I know how much detail to give in future responses if the above isn't enough.
0

Author Comment

This is homework. I am using DrRacket.

So I I understand you correctly, I should have a function that looks something like this?

(define (remove-dups a lst)
((equal? a (car lst)) (remove-dups a (cdr (cdr lst))))
(else (remove-dups (car (cdr lst)) (cdr lst))))

As I said I'm knew to Scheme and recursion for that matter. A tough topic to get my hear wrapped around.

0

LVL 37

Expert Comment

Yes very close. If they are not equal, then you should send car lst as the character though not car (cdr lst). You need to know what the last character was. If you send car (cdr lst) and (cdr list), then the characters will always be equal.

You also need to check if the string is empty first (and of course do nothing in that case).
0

Author Comment

Actually, is there any way to just pass only one parameter -- just the list?
0

Author Comment

Also, what do you mean by do nothing if the string is empty...

Hers's what I'm thinking for a single parameter:

(define (remove-dups lst)
(cond
((null? lst) THEN WHAT??????)
((equal? (car lst) (car(cdr lst))) (remove-dups(cons (car lst) (cdr(cdr lst)))))
(else(remove-dups(cdr lst)))))
0

LVL 37

Accepted Solution

Actually, is there any way to just pass only one parameter -- just the list?

Sure. You could compare car lst to car (cdr lst). If they match, call the function on cdr lst. If they don't match, output car lst and call the function on cdr lst.

Also, what do you mean by do nothing if the string is empty...
Since you keep calling the function on smaller and smaller strings, eventually the string will be empty. In this case, you are done so don't call the function again.
0

Author Comment

How do you actually do nothing? ((null? lst) '()) Is that correct...basically if null then return empty string?

Also, when you say "output car lst", how do you output something? I'm not familiar with any "print" commands in Scheme yet.
0

Author Comment

This is what I have so far...2 different version, which I think do the same thing...but I'm getting this error message:

Highlights in pink:  ((equal? (car lst) ------->  (car(cdr lst))  <-------)
car: expects argument of type <pair>; given '()

(define (remove-dups lst)
(cond
((null? lst) '())
((equal? (car lst) (car(cdr lst))) (remove-dups(cons (car lst) (cdr(cdr lst)))))
(else (car lst) (remove-dups(cdr lst)))))

(define (remove-dups2 lst)
(cond
((null? lst) '())
((equal? (car lst) (car(cdr lst))) (remove-dups2(cdr lst)))
(else (car lst) (remove-dups2(cdr lst)))))
0

Author Comment

Thanks, I figured it out.

Can you take a look at this post please. Thanks for your help.

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

Author Closing Comment

0

## Write Comment

Please enter a first name

Please enter a last name

We will never share this with anyone.

## Featured Post

Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
This is about my first experience with programming Arduino.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

#### 760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!