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?


1 Answer 1


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\$ Dec 30, 2015 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, 2015 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\$ Dec 30, 2015 at 3:51
  • \$\begingroup\$ @morbidCode It goes into the new list that map is building. \$\endgroup\$
    – Barry
    Dec 30, 2015 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\$ Dec 30, 2015 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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