Replacing elements from a list and its sublists

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)

source

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.

(define (substitute l old new)
(if (null? l) '()
(tail (cdr l))
(subl (lambda (x) (substitute x old new))))
((equal? head old) (cons new (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?

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).

map

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)))))

• so on each element you are calling maybe-swap? How does the element get replaced when you return new? – morbidCode Dec 30 '15 at 3:09
• @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. – Barry Dec 30 '15 at 3:34
• 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? – morbidCode Dec 30 '15 at 3:51
• @morbidCode It goes into the new list that map is building. – Barry Dec 30 '15 at 13:19
• 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? – morbidCode Dec 30 '15 at 17:17