Write a procedure substitute that takes three arguments: a list, an old word, and a new word. It should return a copy of the list, but with every occurrence of the old word replaced by the new word, even in sublists. For example:
> (substitute ’((lead guitar) (bass guitar) (rhythm guitar) drums) ’guitar ’axe)
((lead axe) (bass axe) (rhythm axe) drums)


The argument "l" is the list that would be evaluated, I just don't know what name is appropriate because the word "list" is already a procedure. Subl will evaluate the items that are lists.

Please review my code.

(define (substitute l old new)
    (if (null? l) '()
        (let ((head (car l))
            (tail (cdr l))
            (subl (lambda (x) (substitute x old new))))
            (cond ((list? head) (cons (subl head) (subl tail)))
            ((equal? head old) (cons new (subl tail)))
            (else (cons head (subl tail)))))))

How is my use of let and lambda? Did I manage data abstraction correctly? How can I make this code better and faster?


Separate your concerns

Think of it this way - as we walk through the input, we do one of two things. If the next thing is a list, we recurse. If it's not a list, we do the equality checking. You're doing everything in one check, which makes it a little hard to follow.

Let's just define a maybe-swap:

(define (maybe-swap val old new)
    (if (equal? val old) new val))

And use that directly:

(define (substitute lst old new)
    (if (list? lst)
        (map (lambda (elem) (substitute elem old new)) lst)
        (maybe-swap lst old new)))

This does all the same thing that you're doing, but once you split it up, there's less logic to have to reason about. You can even move maybe-swap into substitute directly:

(define (substitute lst old new)
    (define (maybe-swap elem) (if (equal? elem old) new elem))
    (if (list? lst)
        (map (lambda (elem) (substitute elem old new)) lst)
        (maybe-swap lst)))

This also reduces the code duplication. You're currently recursing via (subl X) in four different places. I'm recursing in just one spot - effectively for lists I'm calling (map subl lst).


I think in a previous review you didn't want to use map, which we can easily implement like:

(define (map f lst)
    (if (null? lst) lst
        (cons (f (car lst)) (map f (cdr lst)))))
  • \$\begingroup\$ so on each element you are calling maybe-swap? How does the element get replaced when you return new? \$\endgroup\$ – lightning_missile Dec 30 '15 at 3:09
  • \$\begingroup\$ @morbidCode I don't understand the question. If it helps, think about what happens when you call substitute on a single element, then a list of one or two elements. \$\endgroup\$ – Barry Dec 30 '15 at 3:34
  • \$\begingroup\$ As I understand it, let's say lst is a list, then we call (map (lambda (elem) (substitute elem old new)) lst), now map calls substitute on each element of lst, if substitute found an item that is not a list, it calls (maybe-swap lst), now if (equal? elem old) is true, it returns the new value, otherwise the original value. I'm confused as though where this value that is being returned by maybe-swap go? \$\endgroup\$ – lightning_missile Dec 30 '15 at 3:51
  • \$\begingroup\$ @morbidCode It goes into the new list that map is building. \$\endgroup\$ – Barry Dec 30 '15 at 13:19
  • \$\begingroup\$ regarding map, we can use it as long as we are returning a list with the same length as the original list right? Is it possible to not return all elements based on the predicate of the function argument in map? \$\endgroup\$ – lightning_missile Dec 30 '15 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.