Сортировка атомов списка по частоте появления - Lisp

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

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

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

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

(defun sort-atoms-by-freq (w)
  (sort-atoms (sort (atom-freq w) #'< :key #'cadr)))
 
(defun atom-freq (w &aux (v (remove-duplicates w)))
  (mapcar #'(lambda (a) (list a (count a w))) v))
 
(defun sort-atoms (w &optional ac acc &aux (a (car w)) (d (cdr w)))
  (cond ((null w) (nreverse (cons (caar ac) acc)))
        ((or (null ac) (eq (cadar ac) (cadr a)))
         (sort-atoms d (cons a ac) acc))
        ((sort-atoms d (list a) (cons (if (cdr ac)
                                          (nreverse (mapcar #'car ac))
                                          (caar ac))
                                       acc)))))
 
> (sort-atoms-by-freq '(a a s s s d d f f f f))
((A D) S F)

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

В данном коде реализована функция sort-atoms-by-freq, которая сортирует атомы списка по частоте появления. Список разбивается на атомы и подсчитывается количество вхождений каждого атома в список. Для этого используется вспомогательная функция atom-freq, которая принимает список w и ищет уникальные атомы в этом списке. Затем для каждого атома подсчитывается количество его вхождений в список w. Результатом работы функции atom-freq является список пар атом - количество вхождений. Далее используется вспомогательная функция sort-atoms, которая принимает список w и последовательность кортежей, где каждый кортеж содержит пару атом - количество вхождений. В этой функции используется сортировка по количеству вхождений, а при равном количестве вхождений сортировка происходит по имени атома. Функция sort-atoms реализована рекурсивно и использует тернарный оператор для определения условий выхода из рекурсии. Если список w пуст, то возвращается пустой список. Если список w не пуст, то проверяется, есть ли уже в кортеже ac пара для текущего атома. Если такая пара есть, то рекурсивно вызывается функция sort-atoms для списка d и кортежа, состоящего из текущего атома и пары, найденной в ac. Если такой пары нет, то рекурсивно вызывается функция sort-atoms для списка d и кортежа, состоящего из текущего атома и пустого списка ac. Если список ac пуст, то возвращается список, состоящий из первого элемента кортежа caar ac, иначе возвращается результат рекурсивного вызова функции sort-atoms. Таким образом, результатом работы функции sort-atoms-by-freq будет список, отсортированный по частоте появления атомов.