Определить функцию MERGE которая создает из двух списков цифровых атомов новый отсортированный список - Lisp

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

Определить функцию MERGE которая создает из двух списков цифровых атомов новый отсортированный список. Повторения пропускаются (MERGE ’(3 4 7 8 11) ’(1 4 5 8 15)) -> (1 3 4 5 7 8 11 15)

Решение задачи: «Определить функцию MERGE которая создает из двух списков цифровых атомов новый отсортированный список»

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

;; Двухпутевое слияние
 
(defun merge-2 (lst1 lst2)
  (cond ((null lst1) lst2)
        ((null lst2) lst1)
        ((< (car lst1) (car lst2)) (cons (car lst1) (merge-2 (cdr lst1) lst2)))
        (t (cons (car lst2) (merge-2 lst1 (cdr lst2))))))
 
==> MERGE-2
 
(merge-2 '(1 2 3 4) '(2 3 5 6 7))
 
==> (1 2 2 3 3 4 5 6 7)
 
;; Общее слияние
 
(defun merge (&rest r)
  (cond ((null (cdr r)) (car r))
        (t (let ((tmp (merge-2 (car r) (cadr r))))
             (apply 'merge (cons tmp (cddr r)))))))    
 
==> MERGE
 
(merge '(1 2 3 4) '(2 3 4 5 6) '(-1 0 0 8))
 
==> (-1 0 0 1 2 2 3 3 4 4 5 6 8)
 
(merge '(1 2 3 4) '(2 3 4 5 6) '(-1 0 0 8) '(1 4 8 16 32 64))
 
==> (-1 0 0 1 1 2 2 3 3 4 4 4 5 6 8 8 16 32 64)

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

В коде представлены две функции: merge-2 и merge. Функция merge-2 реализует двухпутевое слияние двух списков. Функция merge реализует общее слияние нескольких списков. Давайте разберем код функции merge-2 по порядку:

(defun merge-2 (lst1 lst2) ...) - определение функции merge-2 с двумя аргументами lst1 и lst2, которые являются списками цифровых атомов.
(cond ((null lst1) lst2) ...) - это конструкция cond, которая проверяет, является ли первый список lst1 пустым. Если это так, то возвращается второй список lst2.
(cond ((null lst2) lst1) ...) - это еще одна конструкция cond, которая проверяет, является ли второй список lst2 пустым. Если это так, то возвращается первый список lst1.
(cond ((< (car lst1) (car lst2)) (cons (car lst1) (merge-2 (cdr lst1) lst2))) ...) - это еще одна конструкция cond, которая сравнивает первый элемент первого списка lst1 с первым элементом второго списка lst2. Если первый элемент lst1 меньше, то возвращается новый список, в котором первый элемент lst1 добавлен в начало, а остальная часть списка lst1 рекурсивно обрабатывается функцией merge-2.
(t (cons (car lst2) (merge-2 lst1 (cdr lst2))))) - это еще одна конструкция cond, которая возвращает новый список, в котором первый элемент lst2 добавлен в начало, а остальная часть списка lst1 рекурсивно обрабатывается функцией merge-2. Теперь рассмотрим код функции merge:
(defun merge (&rest r) ...) - определение функции merge с произвольным числом аргументов r, которые являются списками цифровых атомов.
(cond ((null (cdr r)) (car r)) ...) - это конструкция cond, которая проверяет, является ли последний список в r пустым. Если это так, то возвращается первый элемент последнего списка.
(t (let ((tmp (merge-2 (car r) (cadr r)))) ...)) - это еще одна конструкция cond, которая проверяет, является ли последний список в r не пустым. Если это так, то создается новый список tmp, который является результатом слияния первого элемента первого списка r и первого элемента второго списка r. Затем, с помощью функции apply, новый список tmp объединяется с остальной частью списков r. Таким образом, функция merge рекурсивно объединяет несколько списков в один отсортированный список.