Инверсия атомов для заданного списка - Lisp

Формулировка задачи:

Инверсия состоит в замене местами атома самого высокого уровня атомом самого низкого уровня. Количество атомов на обоих уровнях одинаково. Имена атомов на указанных уровнях различны. Пример 1.

(a (b (c)) d (e (f))) ==>(c (b (a)) f (e (d)))

Решение задачи: «Инверсия атомов для заданного списка»

Листинг программы

;; Список пар (уровень атом)
 
(defun lv-list (lst &optional (lv 0) (r nil))
  (cond ((null lst) r)
        ((atom (car lst)) (lv-list (cdr lst) lv (cons (list lv (car lst)) r)))
        (t (let ((rr (lv-list (car lst) (+ lv 1) nil)))
              (append rr (lv-list (cdr lst) lv r))))))  
 
==> lv-list
 
(lv-list '(a (b (c)) d (e (f))))
 
==> ((2 c) (1 b) (2 f) (1 e) (0 d) (0 a))
 
;; Список внутренних и внешних  атомов
 
(defun max-min (lst)
   (let* ((lvl (mapcar 'car lst))
          (ma  (apply 'max lvl))
          (mi  (apply 'min lvl)))
    (list (mapcar 'cadr (remove-if #'(lambda (x) (< (car x) ma)) lst))
          (mapcar 'cadr (remove-if #'(lambda (x) (> (car x) mi)) lst)))))
 
 
==> max-min
 
(max-min (lv-list '(a (b (c)) d (e (f)))))
 
==> ((c f) (d a))
 
;; Замена
 
(defun repl-atom (lst x y)
  (mapcar #'(lambda (z)
              (cond ((eq z x) y)
                    ((eq z y) x) 
                    ((listp z) (repl-atom z x y))
                    (t z))) lst))
 
==> repl-atom
 
(repl-atom '(a s d (j u) ((jj))) 'j 'jj)
 
==> (a s d (jj u) ((j)))
 
;; Решение задачи:
 
(defun task (lst &optional (ma-mi (max-min (lv-list lst))))
  (cond ((and (null (car ma-mi)) (null (cadr ma-mi))) lst)
        (t (let ((x (caar ma-mi))
                 (y (car (cadr ma-mi))))
             (task (repl-atom lst x y) (list (cdr (car ma-mi)) (cdr (cadr ma-mi))))))))
 
==> task
 
(task '(a (b (c)) d (e (f))))
 
==> (f (b (d)) c (e (a)))

Объяснение кода листинга программы

lv-list - функция, которая принимает список и два опциональных параметра, первый из которых - уровень атомов, а второй - результат предыдущего вызова функции. Если список пуст, возвращается результат предыдущего вызова. Если первый элемент списка - атом, то добавляется новый элемент с уровнем и атомом, а результат предыдущего вызова обновляется. Если первый элемент списка - не атом, то рекурсивно вызывается функция lv-list для его первого элемента, уровень увеличивается на единицу, а результат предыдущего вызова объединяется с новым списком, начинающимся с добавленного элемента.
max-min - функция, которая принимает список и возвращает два элемента: максимальный и минимальный уровень атомов в списке. Сначала создается список уровней атомов, затем с помощью функции max находится максимальное значение уровня, а с помощью функции min - минимальное значение уровня. Затем из списка удаляются элементы с уровнем, меньшим максимального значения, и добавляются элементы с уровнем, большим минимального значения.
repl-atom - функция, которая принимает список и три элемента: старый атом, новый атом и уровень, и заменяет все вхождения старого атома на новый атом на указанном уровне. Если элемент - атом, и он соответствует старому атому, он заменяется на новый атом. Если элемент - список, функция рекурсивно вызывается для каждого его элемента.
task - функция, которая принимает список и два опциональных параметра: список пар внутренних и внешних атомов и список пар уровней внутренних и внешних атомов. Если список пуст, возвращается результат предыдущего вызова. Если первый элемент списка - атом, то он заменяется на второй элемент пары внешних атомов, а результат предыдущего вызова передается следующей итерации. Если первый элемент списка - не атом, то рекурсивно вызывается функция task для его первого элемента, уровень увеличивается на единицу, а результат предыдущего вызова объединяется с новым списком, начинающимся с добавленного элемента.