Racket/Scheme - Replacing an item with another element in a non flat list

Question

I'm trying to replace an item with another item when given a list. I've gotten to code out a procedure that can do this for a flat list but I was not sure how to implement it when the list is not a flat list. This is the current code for the replacer:

(define repl
  (lambda (exp1 exp2 exp3)
    (cond
      ((null? exp3) exp3)
      ((equal? (first exp3) exp1) (cons exp2 (repl exp1 exp2 (rest exp3))))
      (else (cons (first exp3) (repl exp1 exp2 (rest exp3)))))))

I'm very new to coding in racket so I wasn't sure how I would then be able to apply this when it's not a flat list A valid test case is the following

(repl 'a 'b '((f a) (f (a)))) => '((f b) (f (b)))

But when I run my current procedure it produces

'((f a) (f (a)))

How would I go about applying my current code to work for non flat lists?

Answer 1

You need to consider a new case in the recursion: what if the current element in the list is another list? in that case, we need to do a deeper recursion, and descend over both the current element and the rest of the list. Otherwise, check if the current element needs to be replaced, or leave it alone. This is what I mean, notice that this is a faster solution when we only want to replace atoms:

(define repl
  (lambda (exp1 exp2 exp3)
    (cond
      ; base case: list is empty
      ((null? exp3) exp3)
      ; base case: current element is an atom
      ((not (pair? exp3))
       ; should we replace current element?
       (if (equal? exp3 exp1) exp2 exp3))
      ; recursive case: current element is a list
      (else
       ; recursively descend over both sublists
       (cons (repl exp1 exp2 (first exp3))
             (repl exp1 exp2 (rest exp3)))))))

It works as expected, no matter how deeply nested is the element that you want to replace:

(repl 'm 'x '((a (b (c (d e (f (m))) h) i (j) (k (l (m)))) n) o (p)))
=> '((a (b (c (d e (f (x))) h) i (j) (k (l (x)))) n) o (p))

EDIT: Now, if the elements you want to replace are lists themselves, we have to shuffle around the conditions. Below you'll find the implementation, it's more general than my previous solution, but also it's slower. Thanks to @amalloy for suggesting this approach:

(define (repl exp1 exp2 exp3)
  (cond ; base case: list is empty
        ((null? exp3) exp3)
        ; base case: current element is the one we're looking for
        ((equal? exp1 exp3) exp2)
        ; recursive case: current element is a list
        ((pair? exp3) (cons (repl exp1 exp2 (first exp3)) 
                            (repl exp1 exp2 (rest exp3))))
        ; base case: current element is not the one we're looking for
        (else exp3)))

For example:

(repl '(f (g)) 'x '((a (b (c (d e (f (g))) h) i (j) (k (l (m)))))))
=> '((a (b (c (d e x) h) i (j) (k (l (m))))))