By morbidCode

2015-12-29 16:19:56 8 Comments

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?


@Barry 2015-12-29 17:02:49

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

@morbidCode 2015-12-30 03:09:18

so on each element you are calling maybe-swap? How does the element get replaced when you return new?

@Barry 2015-12-30 03:34:21

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

@morbidCode 2015-12-30 03:51:27

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?

@Barry 2015-12-30 13:19:59

@morbidCode It goes into the new list that map is building.

@morbidCode 2015-12-30 17:17:35

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?

@Barry 2015-12-30 17:26:42

@morbidCode map does one thing. If you want to do something else, you use a different tool.

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] Remove first occurrence of element from list

  • 2013-10-29 22:17:15
  • ricardo
  • 2474 View
  • 2 Score
  • 1 Answer
  • Tags:   scheme

2 Answered Questions

[SOLVED] Combinations of list elements

2 Answered Questions

[SOLVED] Faster generation of list with multiple sublists

2 Answered Questions

[SOLVED] Remove the last occurrence of an item in a list

  • 2016-10-16 14:56:16
  • misha
  • 3146 View
  • 3 Score
  • 2 Answer
  • Tags:   scheme

2 Answered Questions

[SOLVED] SICP - exercise 2.27 - reversing elements of a list and sublists

1 Answered Questions

[SOLVED] Replacing elements from a list and its sublists - part II

2 Answered Questions

[SOLVED] SICP - exercise 2.20 - same-parity

1 Answered Questions

[SOLVED] Replacing words from a sentence

1 Answered Questions

[SOLVED] Iterate over large list of lists and replace its elements

1 Answered Questions

[SOLVED] Extracting values from a list

  • 2014-12-11 08:00:15
  • KRC
  • 83 View
  • 1 Score
  • 1 Answer
  • Tags:   scheme racket

Sponsored Content