Создание пользовательского реверса списка

Проблемы

(краткое содержание предыдущих комментариев)

1. Плохие отступы, пробелы и имена; предпочитаю это:

   (defun new-union (l1 l2)
     (setq list (union l1 l2))
     (let (reversed) 
       (loop for x in list
             do (setq res (cons (car list) reversed))
             do (setq list (cdr list)))))
   

2. Использование SETQ для необъявленных глобальных переменных вместо LET

3. Мутация итерируемой структуры (СПИСОК)
4. Не использовать X внутри LOOP (зачем его определять?)
5. Возвращаемое значение всегда NIL

Рефакторинг

(defun new-union (l1 l2)
  (let ((reverse))
    (dolist (elt (union l1 l2) reverse)
      (push elt reverse))))

• Определите локальную переменную reverse, привязанную к NIL по умолчанию (вы можете установить ее в '(), иногда это предпочтительнее).
• Используйте DOLIST для перебора списка и выполнения побочных эффектов; третий аргумент — это возвращаемое значение; здесь можно поставить переменную reverse, где мы будем накапливать перевернутый список.
• Для каждого элемента elt поместите его перед reverse; если вы хотите избежать push в учебных целях, используйте (setf reverse (cons elt reverse)).

Common Lisp является многопарадигмальным и предпочитает прагматичные решения: иногда цикл более естественен или более эффективен, и нет причин заставлять себя принимать функциональный стиль.

Функциональная реализация

Однако списки обеспечивают естественную индуктивную структуру: в некоторых случаях рекурсивные подходы могут быть более подходящими. Если вы хотите использовать функциональный стиль для обратного вычисления, имейте в виду, что оптимизация хвостового вызова, хотя и общедоступная, не требуется спецификацией языка (это зависит от ваших возможностей реализации и параметров компилятора).

С настройками по умолчанию SBCL устраняет вызовы в последних позициях и устраняет риск переполнения стека при больших входных данных. Но есть и другие возможные способы получить плохие алгоритмические сложности (и расточительный код), если вы не будете осторожны. Следующее - это то, что я бы использовал для определения комбинации объединения и реверса; в частности, я предпочитаю определять локальную функцию с labels, чтобы избежать вызова new-union с фиктивным нулевым параметром. Кроме того, я перебираю список, полученный в результате объединения, только один раз.

(defun new-union (l1 l2)
  (labels ((rev (list acc)
             (etypecase list
               (null acc)
               (cons (rev (rest list)
                          (cons (first list) acc))))))
    (rev (union l1 l2) nil)))

След

  0: (NEW-UNION (A B C) (D E F))
    1: (UNION (A B C) (D E F))
    1: UNION returned (C B A D E F)
    1: (REV (C B A D E F) NIL)
      2: (REV (B A D E F) (C))
        3: (REV (A D E F) (B C))
          4: (REV (D E F) (A B C))
            5: (REV (E F) (D A B C))
              6: (REV (F) (E D A B C))
                7: (REV NIL (F E D A B C))
                7: REV returned (F E D A B C)
              6: REV returned (F E D A B C)
            5: REV returned (F E D A B C)
          4: REV returned (F E D A B C)
        3: REV returned (F E D A B C)
      2: REV returned (F E D A B C)
    1: REV returned (F E D A B C)
  0: NEW-UNION returned (F E D A B C)

Примечание

Весьма неожиданно изменить результат union, когда объединение должно работать для неупорядоченных наборов: порядок элементов в результате не должен каким-либо образом отражать порядок списка-1 или списка-2. Наборы — это неупорядоченные наборы, не имеющие дубликатов; если ваши входные списки уже представляют наборы, как намекает имя функции (new-union), то нет смысла удалять дубликаты или ожидать, что порядок будет осмысленным.

Если вместо этого входные списки представляют собой последовательности значений, то порядок имеет значение; не стесняйтесь использовать append или concatenate в сочетании с remove-duplicates, но обратите внимание, что последний по умолчанию удалит элементы перед списком:

(remove-duplicates (concatenate 'list '(4 5 6) '(2 3 4)))
=> (5 6 2 3 4)

Вместо этого вы можете использовать :from-end t.

Хорошо... Я думаю, вы хотите взять два списка, объединить их вместе, удалить дубликаты, а затем поменять их местами.

Ваша самая большая проблема в том, что вы используете циклы вместо рекурсии. LISP был создан для обработки списков с использованием рекурсии. Это гораздо естественнее.

Ниже приведен очень простой пример того, как это сделать:

(defvar l1 '(a b c))      ;first list
(defvar l2 '(d e f))      ;second list

(defun my-reverse (a b)   ;a and b are lists
  "combines a and b into lst, removes duplicates, and reverses using recursion"
  (let ((lst (remove-duplicates (append a b))))   
    (if (> (length lst) 0)
        (append (last lst) (my-reverse nil (butlast lst)))
        nil)))

Пример запуска, скомпилированный в SLIME с использованием SBCL

; compilation finished in 0:00:00.010                                                                                                                                    
CL-USER> l1 ;; verify l1 variable
(A B C)                                                                                                                                                                  
CL-USER> l2 ;; verify l2 variable
(D E F)                                                                                                                                                                  
CL-USER> (append l1 l2) ;; append l1 and l2
(A B C D E F)                                                                                                                                                            
CL-USER> (my-reverse l1 l2) ;; reverse l1 and l2
(F E D C B A)