Lisp Swap function-CodePudding

I am trying to write a functional program in Lisp that requires any two elements of a list to be shaped and return the new list. So far I have:

(defun swap (lst x y)
  (let ((temp (nth y lst)))
   (substitute (nth x lst) (nth y lst))
   (substitute temp (nth x lst)))

When I run: (swap '(1 2 3 4 5 e 6 7 8) 5 4) I get:

*** - EVAL/APPLY: too many arguments given to SWAP

CodePudding user response：

You should decide whether your swap will modify old list or not.

Destructive swap can be done with already mentioned rotatef or with pair of setf:

(defun swap1 (lst i j)
  (let ((temp (nth i lst)))
    (setf (nth i lst) (nth j lst))
    (setf (nth j lst) temp)
    lst))

Non-destructive swap has to work with copy of argument:

(defun swap2 (lst i j)
  (let* ((newlist (copy-tree lst))
         (temp (nth i newlist)))
    (setf (nth i newlist) (nth j newlist))
    (setf (nth j newlist) temp)
    newlist))

CodePudding user response：

remarks

Your code looks a bit like it was inspired by Scheme: you named the variable lst and introduced a local variable as-if with define but in a way that does not work in Common Lisp, where let is scoped. Moreover, you do not use the return value of SUBSTITUTE, which means that any intermediate result is discarded. The substitute function is purely functional and do not change its inputs with side-effects.

(defun swap (lst x y)
  (let (temp (nth y lst))) ;; temp is only visible inside the let
  (substitute (nth x lst)  (nth y lst)) ;; result is discarded
  (substitute temp (nth x lst))) ;; <- the only thing actually used in swap

implementing swap

There are two possible versions for this function, one that mutates the input list, one that doesn't. You also have to decide what is or isn't a valid input and what happens when an invalid input is given.

In both cases below, I assume that x is strictly lower than y, you can make the function more robust by swapping x and y in case this is not the case, or simply returning lst when x and y are equal.

Note also that in case x and/or y are beyond the limit of the list, the result is going to contain NIL values or signal an error, you could add more checks in the below functions to avoid those problems.

destructive version

Here, nswap is the destructive version, it descends into the list x times using nthcdr, to the sublist that starts at position x. From this sublist, it descends the remaining amount of cells to reach position y. The two lists xlist and ylist are lists that start at respectively position x and y. Then, I exchange their car using ROTATEF.

(defun nswap (list x y)
  (assert (< x y))
  (let* ((xlist (nthcdr x list))
         (ylist (nthcdr (- y x) xlist)))
    (prog1 list
      (rotatef (car xlist)
               (car ylist)))))

functional version

The purely functional swap could just call nswap on (copy-list lst). It is however also possible to share some cells with lst, since everything that follows the rest of ylist is left unmodified. That's how the function works, it computes xlist and ylist as before, but uses LDIFF to produce fresh lists (regions of the initial list). The different slices of the initial lists are concatenated with nconc (they are fresh lists, so the code has local side-effects but externally, the input list is unmodified). The (rest ylist) is the last argument to nconc and is not a copy.

(defun swap (list x y)
  (assert (< x y))
  (let* ((xlist (nthcdr x list))
         (ylist (nthcdr (- y x) xlist)))
    (nconc (ldiff list xlist)
           (list (first ylist))
           (ldiff (rest xlist) ylist)
           (list (first xlist))
           (rest ylist))))

For example, using :circle t for write let us see the shared end of list:

(let ((list '(a b c d e f g h i)))
  (write (list :original list
               :swapped (swap list 1 3))
         :circle t))

The following is printed, with #1= marking the tail and #1# showing that the identical same tail is used in the result:

(:ORIGINAL (A B C D . #1=(E F G H I))
 :SWAPPED (A D C B . #1#))