Основи мови програмування Лісп, Детальна інформація

Основи мови програмування Лісп
Тип документу: Реферат
Сторінок: 7
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 13.7
Скачувань: 1092
Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку. Інтуїтивно необхідно порівняти символ з першим елементом списку, потім з другим елементом і так далі. Проблема в такому розв’язку виникає в тому, що ми не знаємо наперед довжини списку. А якщо ми і знаємо цю довжину, і якщо вона велика, то тіло функції буде дуже великим. Така функція буде мати приблизно такий вигляд (перший стовпчик):

$ (DEFUN MEMBER (nam lst) $ (DEFUUN MEMBER (nam lst)

((EQL nam (FIRST lst))) ((NULL lst) NIL)

((EQL nam (SECOND lst))) ((EQL nam (CAR lst)) T)

((EQL nam (THIRD lst))) (MEMBER nam (CDR lst)) )

((EQL nam (THIRD (CAR lst))))

. . . . . . . . . . . . . . .

Змінимо наш підхід до побудови функції. В другому стовпчику побудовано функцію MEMBER, в основі якої лежить рекурсивний підхід, який базується на наступних фактах:

1. Якщо список порожній (не має елементів), то nam не належить списку.

2. Якщо nam дорівнює голові списку, то nam належить списку.

3. Якщо nam не дорівнює голові списку, то nam може належити списку тоді і тільки тоді коли nam належить хвосту списку.

Розглянемо дві рекурсивні функції: REMBER (REMove memBER), яка має два аргументи — атом obj та список lst і яка видаляє перше зустрічання атома obj в списку lst. REMBER-ALL яка видаляє всі атоми obj в списку lst.

$ (DEFUN REMBER (obj lst) (DEFUN REMBER-ALL (obj lst)

((NULL lst) NIL) ((NULL lst) NIL)

((EQL obj (CAR lst)) (CDR lst)) ((EQL obj (CAR lst))

(CONS (CAR lst) (REMBER-ALL obj (CDR lst))

(REMBER obj (CDR lst))) ) (CONS (CAR lst)

(REMBER-ALL obj (CDR lst))))

Результат роботи цих функцій проілюструємо на прикладах:

$ (REMBER ‘a ‘(q a w e r t a y)) $ (REMBER-ALL ‘a ‘(q a w e r t a y))

(q w e r t a y) (q w e r t y)

Примітивна функція EQL використовується для порівняння атомів. Часто виникає потреба порівнювати списки. Напишемо функцію EQLIST, яка порівнює списки. Її побудуємо на основі наступних фактів:

1. Якщо перший список порожній, то, якщо і другий список порожній, повернути Т, інакше повернути NIL (або просто повернути (NULL другого списку)).

2. Якщо другий список порожній, повернути NIL.

3. Якщо голова першого списку не дорівнює голові другого списку, повернути NIL.

4. Перевірити рівність хвостів першого та другого списків.

$ (DEFUN EQLIST (lst1 lst2) $ (DEFUN NOT (obj)

((NULL lst1) (NULL lst2)) (EQL obj NIL) )

((NULL lst2) NIL)

((NOT (EQL (CAR lst1) (CAR lst2))) NIL)

The online video editor trusted by teams to make professional video in minutes