Засоби та принципи програмування на Ліспі

Наведену функцію можна визначити наступним чином (ім’я змінено на MAKE-LST):

(DEFUN MAKE-LST (N OBJ LST)

((AND (INTEGERP N) (PLUSP N))

(CONS OBJ (MAKE-LIST (SUB1 N) OBJ LST)) )

LST )

Функця (OBLIST) що не має аргументів, утворює та повертає список активних на поточний момент символів у системі. Символи розташовані в тому порядку, в якому вони прочитані або згенеровані строковими функціями: нові символі розташовані зліва від старих.

4. Породження комбінаторних об’єктів.

Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.

1. Надрукувати всі послідовності довжини n з цифр 0,1. (P11 n).

Функція P11 викликається з одним аргументом n, аргумент lst – допоміжний.

(DEFUN p11 (n lst)(DEFUN p13 (n lst)

((ZEROP n) (PRIN1 lst) (TERPRI))((ZEROP n) (PRN13 lst) (TERPRI))

(P11 (- n 1) (CONS 0 lst))(P13 (- n 1) (CONS 0 lst))

(P11 (- n 1) (CONS 1 lst)) )(P13 (- n 1) (CONS 1 lst)) )

2. Надрукувати всі послідовності довжини k з чисел 1..n. (P12 k n).

Друкуватимемо послідовності у лексикографічному порядку. За допомогою функції (GEN1 n) згенеруємо список з n елементів, кожен з яких дорівнює 1. Список lst зберігатиме поточну перестановку. Функція (NEXT lst n) знаходить перестановку, яка буде наступною після lst. Функція P12BEST є найкращим рекурсивним розв’язком цієї задачі.

(DEFUN GEN1 n)

((ZEROP n) NIL)

(CONS 1 (GEN1 (- n 1))) )

(DEFUN NEXT (lst n)

((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))

((NULL (CDR lst)) NIL)

(CONS 1 (NEXT (CDR lst) n))

Шукана функція має вигляд: