How to get the value of an item in a list at a certain position?

Question

I need to create a function that replaces all occurrences of X and Y with Z in list L. My problem is that my compare statement is comparing to the position itself from what I understand.

Similar to how an I value would work when looping in other languages? When I run this code it replaces the item at position 3 and position 7: (2 2 2 6 4 5 8 4 5 8 4) (2 2 7 6 4 5 7 4 5 8 4) instead of doing what it's supposed to. So I need to figure out how to compare the value at that position instead of the position itself.

If I put a print statement in place of the (replace) function it'll print 2 2 2 6 so I don't really understand that. I have also tried (setf (nth Y Z) i) instead of the replace function with the same outcome, that's how I've been able to figure out the problem is with the compare statement. I've also tried using eq, =, and equal with all the same outcome.

 (defun replace-z (X Y Z L)


 (loop for i in L
 do 
 (cond

 ((equal Y i) (replace L (list Z) :start1 i))

 ((= X i) (replace L (list Z) :start1 i)))) L) 
 (trace replace-z)
 (print (replace-z 2 6 7 '(2 2 2 6 4 5 8 4 5 8 4) ))

Answer 1

Because CL is an industrial strength language, there are several functions already provided by the language to do things like this. However from the point of view of learning Lisp it's good to think about what the algorithm you would need to use to write something to do this if it did not already exist, and then actually implement that using basic operations rather than use one of the functions which already do it: doing this teaches you to program in Lisp, while finding & using the preexisting tool teaches you to look things up in manuals, and these are different skills.

Using recursion to solve the problem

So what's the algorithm?

Given a list l:

• if it is the empty list, we're done;
• if it is not empty then split it into its first element and the rest of it;
• if the first element is X or Y then the result is (cons 'Z ...) otherwise it is (cons <existing first element> ...), where ... means 'perform the same procedure on the rest of the list'.

So we can turn this into code immediately:

(defun replace-x/y-with-z (l)
  (if (null l)
      l
    (cons (if (or (eql (first l) 'x)
                  (eql (first l) 'y))
              'z
            (first l))
          (replace-x/y-with-z (rest l)))))

Well, this function is ugly in several ways: one of them is that it calls first a lot. We can deal with this by binding a local variable. And we can also neatly replace the hairy conditional with case:

(defun replace-x/y-with-z (l)
  (if (null l)
      l
    (let ((first (first l)))
      (cons (case first
              ((x y) 'z)
              (otherwise first))
            (replace-x/y-with-z (rest l))))))

And then we can get carried away and decide that we want to make this general, using member:

(defun replace-things-with-thing (l things thing &key (test #'eql))
  (if (null l)
      l
    (let ((first (first l)))
      (cons (if (member first things :test test)
                thing
              first)
            (replace-things-with-thing (rest l) things thing :test test)))))

And all of this is avoiding the elephant in the room: none of these functions really work properly. They don't work properly because they are recursive, and in due course they will run out of stack.

Using mapping to solve the problem

If we want such a function to work in any conforming CL we need either to write them in an explicitly iterative way, or using primitives which CL warrants as working on even very long lists. To do that we need to think about a different algorithm. Here's that algorithm:

Given a function f of one argument defined so that:

• if the argument is X or Y the value is Z;
• otherwise the values is the argument.

Then map this function over the list.

And this is what mapcar does. So now:

(defun replace-x/y-with-z (l)
  (mapcar (lambda (e)
            (case e
              ((x y) 'z)
              (otherwise e)))
          l))

And this is a nice easy-to-understand function which does what we want.

And again we can generalise this:

(defun replace-things-with-thing (l things thing &key (test #'eql))
  (mapcar (lambda (e)
            (if (member e things :test test)
                thing
              e))
          l))

This is a pretty nice, general, solution I think: I like this answer best

---

Some more extreme approaches

Using tail recursion

Of course, if we were using a language which, at the language level, promised to turn suitable recursive procedures into iterative ones, we could write a tail-recursive version of this and feel all clever. But in fact the version using mapcar is nicer I think, because tail-recursive versions of these things return their results backwards and they then have to be reversed. But there's still a place where we can write a nice, naturally-tail-recursive function which will help: member.

An element is a member of a list if:

• the list is not empty, and
  • it is equal (for some definition of 'equal') to the head of the list
  • or it is a member of the tail of the list.

And we can write this function:

(defun memp (elt list &key (test #'eql))
  (if (null list)
      nil
    (or (funcall test elt (first list))
        (memp elt (rest list) :test #'eql))))

This function is tail recursive, and thus any implementation which eliminates tail calls will turn it into iterative code. We could use this function above instead of member (note that it does not return quite the same result that member does: member returns the tail of the list).

And finally, if you want to get all fancy and worry about performance you can write memp in such a way that you don't have to keep worrying about keyword arguments &c, using a local function:

(defun memp (elt list &key (test #'eql))
  (labels ((memp-loop (tail)
             (if (null tail)
                 nil
               (or (funcall test elt (first tail))
                   (memp-loop (rest tail))))))
    (memp-loop list)))

This idiom is so common in Scheme – a language which does eliminate tail calls – that there is special syntax for it (below code is Racket):

(define (mem? elt lst #:test (test? eqv?))
  (let mem-loop ([tail lst])
    (if (null? tail)
        #f
        (or (test? elt (first tail))
            (mem-loop (rest tail))))))

The extremist's approach

Finally, let's look at an approach which I'll call the extremist-language-learning approach: let's assume that we really want to implement all of the functionality we need to do this ourselves, relying only on very basic facilities provided by the language. In particular we're going to allow ourselves these facilities:

• assume the language turns tail calls into iteration;
• conditionals with cond & if (we could easily just use one of these);
• list facilities – null, first, rest, cons;
• equality test – eql (provided as an argument);
• funcall because CL is a Lisp-2 (not needed in a Lisp-1);
• local functions with labels – we could define all the helper functions globally but it's just nicer to package them all inside a single function.

And in addition we'll use fancy argument processing once, for the top-level function.

We are not allowed to use any functions which map over lists, or anything like that: all those we need to write.

With those restrictions we end up with something like this horror:

(defun replace-things-with-thing (l things thing &key (test #'eql))
  ;; an absurdly purist, tail recursive version
  (labels ((memp (e tail)
             ;; is E in TAIL compared using TEST.  In real life this
             ;; would be MEMBER
             (cond ((null tail)
                    nil)
                   ((funcall test e (first tail))
                    t)
                   (t (memp e (rest tail)))))
           (rev (tail accum)
             ;; reverse TAIL. In real life this would be REVERSE
             (if (null tail)
                 accum
               (rev (rest tail) (cons (first tail) accum))))
           (replace-loop (tail accum)
             ;; the implementation of the function
             (if (null tail)
                 ;; we're done: the reverse of ACCUM is the answer
                 (rev accum '())
               (let ((e (first tail)))
                 (replace-loop (rest tail)
                               (cons (if (memp e things)
                                         thing
                                       e)
                                     accum))))))
    (replace-loop l '())))

I think you could argue that writing something like this helps you learn Lisp. I'm not sure it's true though.

(And you can go further than this of course: the real purist would use the Y combinator here, and if you think that helps you learn the language, well.)

Answer 2

The function you're trying to write already exists as a standard function in ANSI Common Lisp.

substitute looks for a single object to replace; to look for any one of a set of values, we can use substitute-if, with a predicate that tests for those two.

(substitute-if #\c (lambda (x) (member x '(#\a #\b))) "How about it?")
--> "How ccout it?"

(substitute-if 42 (lambda(x) (or (= x 0) (= x 1))) '(0 1 2 3 0 1))
--> (42 42 2 3 42 42)

If you really intend to modify the sequence in-place, there is nsubstitute-if.

Using loop we can do:

(loop for x in '(0 1 2 3 0 1)
      if (or (= x 0) (= x 1))
        collect 42
      else
        collect x)
--> (42 42 2 3 42 42)

Unfortunately, loop needs different syntax to traverse a vector: for x across ...

To do the above loop replacement in-place, we change in to on. Then x traverses the cons cells of the list, rather than the cars of those cons cells.

(loop with l = (list 0 1 2 3 0 1)
      for c on l       ; c means "cell"
      for x = (car c)
      if (or (= x 0) (= x 1)) do
        (rplaca c 42)
      finally (return l))
--> (42 42 2 3 42 42)

Answer 3

My problem is that my compare statement is comparing to the position itself from what I understand.

When you do (loop for i in L), i takes successively the value of each element in L. You could add a clause like this (loop for p from 0 for i in L) to also declare a counter p which represents the current position in the list.

In replace the :start1 argument wants a position, so you do not want to give it i, but p instead, though this is not the most elegant way to solve the problem, as you iterate over L while iterating over it: this has quadratic run time for something which only requires a single pass over L.

By the way, I don't think you are supposed to use replace in this exercise. The point of replace is to be able to do that (copy-seq is required to avoid modifying literal data):

 (replace (copy-seq "---------") "ooo" :start1 2)
 => "--ooo----"

If you wanted to use existing standard functions, you could use substitute-if; for example:

(defun replace-z (x y z l)
  (let ((to-replace (list x y)))
    (flet ((replacep (v) (member v to-replace)))
      (substitute-if z #'replacep L))))

If I put a print statement in place of the (replace) function it'll print 2 2 2 6 so I don't really understand that

The resulting code would be:

(defun replace-z (X Y Z L)
  (loop
     for i in L
     do (cond
          ((equal Y i) (print i))
          ((= X i) (print i))))
  L)

Note that the final L is hard to notice (at least to me), maybe the return value could be made a little more explicit by using existing constructs in loop:

(defun replace-z (X Y Z L)
  (loop
     for i in L
     when (or (equal y i) (= x i))
     do (print i)
     finally (return L)))

What happens is that you print the value i when it is equal to either x or y (note that = and equal compare differently), which is why your output is 2 2 2 6.

I've also tried using eq, =, and equal with all the same outcome.

Do not use eq for numbers and characters, as it is permitted for implementations to have (eq x x) return NIL for values which are otherwise eql (for example, bignum integers).