2.4 Вычисление факториала числа

Известно, что

n!=(n-1)!*n, 0!=1

Используем этот факт для решения поставленной задачи.

(DEFUN FAKTORIAL (N)

(COND ((ZEROP N) 1)

(T (TIMES N (FACTORIAL (SUB1 N))))

)

)

2.5 Вычисление длины списка

Требуется вычислить длину списка. Список состоит из элементов, длина списка - количество этих элементов.

Идея: Проверяем является ли список X пустым, тогда длина списка = 0. Если X – не пустой список, то его длина равна длина списка X без первого элемента +1.

(DEFUN LENGTH (X)

(COND ((NULL X) 0)

(T (ADD1 (LENGTH (CDR X))))))

2.6 Вычисление длины списка и его подсписков

(DEFUN FULLLENGTH

(COND ((ATOM X) 1)

(T (PLUS (FULLLENGTH (CAR X))

(FULLLENGTH (CDR X)))

)

)

Функция возвращает длину списка увеличенную на 1, т.к. NIL - атом.

Определим теперь, является ли список одноуровневым, т.е. не содержащим подсписков:

(DEFUN ATOMLIST (U)

(COND ((NULL U) T)

((NOT (ATOM (CAR U))) NIL)

(T (ATOMLIST (CDR U)))

)

)

2.7 Соединение списков

Определяемая ниже функция является встроенной для многих реализаций языка ЛИСП.

(APPEND (Х1 … Хn)

(DEFUN APPEND (U V)

(COND ((NULL U) V)

(T (CONS (CAR U) (APPEND (CDR U) V)))

)

)

Функция APPEND вначале в итоговый список добавляет первый аргумент, т.е. копирует первый аргумент, а затем к скопированной структуре присоединяет второй аргумент. В соответствии с таким определением функции, аргумент V может быть не списком. В этом случае, результат - точечная пара.

- обращение к функции APPEND

(A B) (A B C D) 

(C D) 

(B) (B C D)  - диаграмма работы функции

(C D) 

() (C D) 

(C D)

до начала работы функции после работы функции

копирует

A структуру

A

B

B

C

D

Воспользуемся функцией APPEND для линеаризации списка.

(DEFUN LINERIZED (U)

(COND ((ATOM U) U)

((ATOM (CAR U))(CONS (CAR U)(LINERIZED (CDR U))))

(T (APPEND (LINERIZED (CAR U))(LINERIZED (CDR U))))

))

Функция проверяет, является ли U атомом, если да, то возвращает U. Если U - список, то проверяется, является ли атомом первый элемент, если да, то он добавляется в начало линеаризованного остатка списка U. Если первый элемент списка не атом, то он линеаризуется и с помощью APPEND соединяется с линеаризованным остатком списка U.

В языке muLISP имеется стандартная функция:

(LIST Arg1 ... Argn) - объединяет аргументы в один список. Аргументы могут быть и списками. Число аргументов неопредлено,т.е. функция относится к классу FSUBR.

Определим функцию, которая будет обращать список через функцию APPEND.

(DEFUN REVLIST (U)

(COND ((NULL U) NIL)

(T (APPEND (REVLIST (CDR U)) (LIST (CAR U))))

)

)

Если U- не пустой список, то соединяем перевернутый остаток списка U с первым элементом списка U.