Визначення функцій в Ліспі, Детальна інформація

((NULL lst) 10 1) 1 12

(SETQ b 2)

((CDR lst) 12) $ (sm ‘(i)) $ (sm ‘g)

(SETQ b 3) ) 3 3

Як бачимо, після виконання простого завдання керування завжди передається наступному завданню (якщо таке є). Якщо предикат умовного завдання істинний, то виконується його хвіст і повертається результат останнього виразу хвоста.

Вмонтована функція (LIST x1 ... xn) утворює та видає список, елементами якого є x1,..., xn. Якщо аргументи не задані, результатом буде NIL.

$ (LIST ‘a ‘b ‘c ‘d) $ (LIST ‘a ‘(b c) ‘d) $ (LIST)

(a b c d) (a (b c) d) NIL

Напишемо функцію 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)

\x00B2