Scheme procedure to replace elements in a list

Question

I am trying to create a procedure in scheme which replaces a certain element in a list with another element

(define (replace var player list)
  (if (null? list)
      '()
     (if (list? (car list))
                (cons (replace var player (car list))          
                      (replace var player (cdr list))
          (if (equal? var (car list))
              (cons player (replace var player (cdr list)))
              (cons (car list) (replace var player (cdr list)))
          ))))

Currently the procedure does not replace any elements. This is the input list

'(q w (e r (t x)) y u i (o (x)) p x a s d)

I would like to replace the 'x' elements in that list with 'y'.

This is the desired output

'(q w (e r (t y)) y u i (o (y)) p y a s d)

We have tried

(replace_by 'x 'y '(q w (e r (t x)) y u i (o (x)) p x a s d) 

but it does not seem to be working

Answer 1

The posted code is missing one parenth at the end, and has a misplaced parenth. The first cons expression needs to be closed by a parenth:

(define (replace var player list)
  (if (null? list)
      '()
     (if (list? (car list))
         (cons (replace var player (car list))          
               (replace var player (cdr list)))
         (if (equal? var (car list))
             (cons player (replace var player (cdr list)))
             (cons (car list) (replace var player (cdr list)))))))

After these corrections, the OP code works for nested lists where the item to be replaced is a non-list. But, it fails when the item to be replaced is a list. This is because list elements encountered in the input are never checked for equality against var. Note also that it is a bad idea to use list as a formal parameter in Scheme functions; this shadows the built-in list function.

Here is an implementation that will replace both atoms and lists in the input list. Before checking whether the input is an atom, the function checks for equality with old. If the old value is not equal? to the current head value, then the function checks whether the current head value is an atom. If it is, then that atom (which was not equal? to old) is consed onto the result of calling replace on the tail; note that empty lists are considered atoms ('() is both a list and an atom) and have already been handled at this stage. Otherwise, the current head is a non-empty list, and the function descends into both the head and the tail.

Here atom? is used to distinguish between non-empty lists and atoms, with '() being considered an atom. Some Schemes include a definition for atom?, but it is not in R5RS or R6RS Standard Scheme. You can define it yourself if needed:

(define (atom? x)
  (not (pair? x)))

Or you could just use (not (pair? head)) in place of (atom? head) in the code below, which uses atom? because the name seems more descriptive. A let expression is used to reduce the number of calls to car and cdr, and to clarify the intent of the recursive calls to replace:

(define (replace old new xs)
  (if (null? xs)
      xs
      (let ((head (car xs))
            (tail (cdr xs)))
        (cond ((equal? head old)
               (cons new (replace old new tail)))
              ((atom? head)
               (cons head (replace old new tail)))
              (else
               (cons (replace old new head)
                     (replace old new tail)))))))

Here are some sample interactions:

> (replace 'a 'x '(1 2 a 3 4 a))
(1 2 x 3 4 x)

> (replace 'a 'x '(1 2 a (3 4 a (5 a (a (a)) 6 a) ()) a))
(1 2 x (3 4 x (5 x (x (x)) 6 x) ()) x)

> (replace '() 'x '(1 2 a (3 4 a (5 a (a (a)) 6 a) ()) a))
(1 2 a (3 4 a (5 a (a (a)) 6 a) x) a)

> (replace '(5 a (a (a)) 6 a) 'x '(1 2 a (3 4 a (5 a (a (a)) 6 a) ()) a))
(1 2 a (3 4 a x ()) a)

> (replace '(5 a (a (a)) 6 a) '(x (x x)) '(1 2 a (3 4 a (5 a (a (a)) 6 a) ()) a))
(1 2 a (3 4 a (x (x x)) ()) a)