Basic LISP recursive replacement of substring

Question

I'm trying to replace any occurrences of a given string in a list with "X", using basic LISP commands (e.g. no mapcar) in a recursive function.

(defun removetext (symbol list replaced)
    (if (not list)   ; if initial list has been exhausted, return replaced list
        replaced
        (progn
            (if (eql (car list) symbol)   ; otherwise, if first element of list = symbol, replace with "X"
                (removetext symbol (cdr list) (cons "X" replaced)) 
                (removetext symbol (cdr list) (cons (car list) replaced)) ; otherwise keep it 
            )
            (format t "~D" replaced)
        )
    )
)

This does not work if I call it with (removetext "E" '(A B C D E F F E) "").

This returns NIL and the printout looks like (F F E D C B A . )(F E D C B A . )(E D C B A . )(D C B A . )(C B A . )(B A . )(A . ).

I want it to return (A B C D X F F X).

Answer 1

None of the other answers so far have addressed an important problem in your code. Given this slightly different but structurally similar version of your function:

(defun replace-thing (list thing by &key (test #'eql))
  (labels ((replace-it (tail replaced)
             (if (null tail)
                 (reverse replaced)
               (progn
                 (if (funcall test (first tail) thing)
                     (replace-it (rest tail) (cons by replaced)) 
                   (replace-it (rest tail) (cons (first tail) replaced)))
                 (format t "~&got ~S~%" replaced)))))
    (replace-it list '())))

This will fail in the same way as one of the ways yours does:

 > (replace-thing '(a b c) 'a 'c)
 (b c)
 (c)
 nil
nil

And the reason it's failing is because what progn does. You've written

(progn
  ... compute the thing you care about ...
  (format ...))

And the value(s) of progn are the value(s) of the last form in its body, so in this case the value of (format ...) which is nil.

There are two solutions to this: one that works for you and one that is more general.

The solution that works for you is to realise that replaced is never altered (your function does no mutation, which is good), so you can safely print it first:

(progn
  (format t "~& ~S~%" replaced)
  (if (funcall test (first tail) thing)
      (replace-it (rest tail) (cons by replaced)) 
    (replace-it (rest tail) (cons (first tail) replaced))))

This change will make my function work.

A more general solution is to realise that what you want is some form, say first-thing which, when used as

(first-thing
  thing1
  ...
  thingn)

Will:

1. do the things in its body in order;
2. then return the value(s) of the first of them.

Well, you can write such a form pretty easily as a macro. Here's a slightly restricted version:

(defmacro first-thing (thing1 &body more-things)
  (let ((sn (make-symbol "STASH")))
    `(let ((,sn ,thing1))
       ,@more-things
       ,sn)))

Then

> (first-thing 1 (print "hi") (print "there"))

"hi" 
"there" 
1

But in fact you don't need to do that: CL offers both this restricted one and a more general one:

• the restricted one is prog1 – (prog1 thing1 ... thingn) evaluates the things in order and then returns the first value of the first thing;
• the general one is multiple-value-prog1 – (multiple-value-prog1 thing1 ... thingn) evaluates the things in order and then returns all the values of the first one.

multiple-value-prog1 is almost certainly more expensive than prog1 since it needs to stash multiple values somewhere and hence almost certainly conses. In your case you only need prog1 though, so a version of (my version of) your function is:

(defun replace-thing (list thing by &key (test #'eql))
  (labels ((replace-it (tail replaced)
             (if (null tail)
                 (reverse replaced)
               (prog1
                 (if (funcall test (first tail) thing)
                     (replace-it (rest tail) (cons by replaced)) 
                   (replace-it (rest tail) (cons (first tail) replaced)))
                 (format t "~& ~S~%" replaced)))))
    (replace-it list '())))

And

> (replace-thing '(a b c) 'a 'z)
 (b z)
 (z)
 nil
(z b c)

Answer 2

If you want to replace occurrences of a string you'll need to pass a list of strings. You passed a list of symbols, not strings. Now you can still replace those symbols with a particular string, but they are not string themselves. The list:

'(a b c d e f e)

is a list of symbols, not string:

 (defun remove-text (str lst)
   (if (atom lst)
       lst
       (if (string-equal (symbol-name (car lst)) str)
           (cons "X" (remove-text str (cdr lst)))
           (cons (car lst) (remove-text str (cdr lst))))))

We can pass a string as an argument to check, and then a list of symbol. Our base case will test to see if the list is an atom, at which point we will simply return the list. If not, we will use string-equal to see if the symbol name of the car of the list(which will return the string value of the symbol) is equal to our string. Then we can then cons "X" unto the beginning of the list if that is the case, and then recursively call the function again. If not, we can simply cons the car of the list to the beginning of the list, and recursively call the function again. This function is not tail-recursive, but it recursive, and it does avoid creating a new list structure to store thee result, without destructively altering the structure of the original list. We can test it below:

CL-USER> (remove-text "E" '(a b c d e f f e))
(A B C D "X" F F "X")

Answer 3

(defun removetext (symbol list replaced)
  (if (null list)
      (reverse replaced)
    (if (eql (car list) symbol)
        (removetext symbol (cdr list) (cons 'x         replaced)) 
        (removetext symbol (cdr list) (cons (car list) replaced)))))

Example:

CL-USER > (removetext 'E '(A B C D E F F E) ())
(A B C D X F F X)