Работа со словами в форме списков - Lisp

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

Определить с помощью упоминаемого в тексте теоретического раздела (п.5.3) предиката РАНЬШЕ-Р предикат (АЛФАВИТ-Р х у), определяющий стоят ли слова, заданные списком букв, в алфавитном(словарном) порядке. После этого определить функцию (СЛОВАРЬ х), которая сортирует в алфавитном порядке неупорядоченное множество слов. Например,

>(словарь '((Ф у н к ц и я) (цикл) (р е к у р с и я)))
(Р Е К У Р С И Я) (Ф У Н К Ц И Я) (Ц И К Л))

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

>(словарь '((Ф у н к ц и я) (цикл) (р е к у р с и я)))
((Ц И К Л) (Р Е К У Р С И Я) (Ф У Н К Ц И Я))

Предикат РАНЬШЕ-Р проверяет, находится ли элемент А ранее элемента В, в соответствии с расположением, определенным порядком следования элементов в списке ПОРЯДОК:

>(defun РАНЬШЕ-Р (а b порядок)
       (cond ((null порядок) nil)
                ((eq a (car порядок)) t) ;А раньше
                ((eq b (car порядок)) nil) ;В раньше
                (t (РАНЬШЕ-Р a b (cdr порядок)))))
РАНЬШЕ-Р
>(раньше-р 'b 'e '(a b с d е))
Т
>(вставь 'b '(а с d) '(a b с d e))
(А В С D)

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

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

(defun раньше-р (a b порядок) 
  (COND ((NULL порядок) NIL)
        ((EQ a (CAR порядок)) T)
        ((EQ b (CAR порядок)) NIL) 
        (T (РАНЬШЕ-Р a b (CDR порядок)))))
 
(defun cmp-words (w1 w2 seq &optional (ww1 w1) (ww2 w2))
  (cond ((and (null w1) (null w2)) ww1)
        ((and (null w1) w2) ww1)
        ((and (null w2) w1) ww2)
        ((eq (car w1) (car w2)) (cmp-words (cdr w1) (cdr w2) seq ww1 ww2))
        ((РАНЬШЕ-Р (car w1) (car w2) seq) ww1)
        (t ww2))) 
 
(defun min-word (wlist seq &optional (minw (car wlist)))
  (cond ((null wlist) minw)
        (t (min-word (cdr wlist) seq (cmp-words (car wlist) minw seq)))))
 
 
(defun sort-words (wlist seq)
  (cond ((null wlist) nil)
        (t (let ((minw (min-word wlist seq)))
           (cons minw (sort-words (removef minw wlist) seq))))))
 
(sort-words '((b o t) (b a t t) (a 1) (a 0))  '(0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z))
 
==> ((a 0) (a 1) (b a T T) (b o T))

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

В коде представлено несколько функций для работы со словами в форме списков на языке Lisp.

ранее-р — функция, принимающая три аргумента: a, b и порядок. Если порядок — это пустой список, то возвращается NIL. Если первый элемент порядка равен a, то возвращается T. Если первый элемент порядка равен b, то возвращается NIL. В противном случае функция рекурсивно вызывается с CDR порядка в качестве нового порядка.
cmp-words — функция, принимающая пять аргументов: w1, w2, seq и два необязательных аргумента ww1 и ww2. Если w1 и w2 оба NULL, то возвращается ww1. Если w1 NULL, а w2 нет, то возвращается ww2. Если первый элемент w1 равен первому элементу w2, то функция рекурсивно вызывается с CDR w1 и CDR w2 в качестве новых значений w1 и w2. Если первый элемент w1 идет перед первым элементом w2 в seq, то возвращается ww1. В противном случае возвращается ww2.
min-word — функция, принимающая четыре аргумента: wlist, seq и два необязательных аргумента minw и ww1. Если wlist NULL, то возвращается minw. Если wlist не NULL, то функция рекурсивно вызывается с CDR wlist и seq в качестве новых значений wlist и seq, а minw передается как minw в следующую итерацию.
sort-words — функция, принимающая два аргумента: wlist и seq. Если wlist NULL, то возвращается NIL. Если wlist не NULL, то функция рекурсивно вызывается с CDR wlist и seq в качестве новых значений wlist и seq, а minw передается как minw в следующую итерацию. В основной части кода вызывается функция sort-words с аргументами '((b o t) (b a t t) (a 1) (a 0)) и '0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z'. Функция sort-words рекурсивно вызывается для каждого элемента в wlist. В этом процессе min-word используется для определения текущего минимального элемента, а cmp-words используется для определения порядка элементов. В конце функция возвращает отсортированный список. В результате выполнения кода будет возвращен отсортированный список: ((a 0) (a 1) (b a T T) (b o T)).