Функциональное программирование и интеллектуальные системы
..pdf
31
Пример вызова функции:
(MEMBER 'Q '(A S Q E D)) ==> (Q E D)
Рассмотрим поэтапное вычисление следующего обращения к функции: (MEMBER 'Q '(A S Q E D)). В теле функции будет вычисляться следующее выражение:
1.Так как Y не является пустым списком и Q не равно A, то (MEMBER `Q `(S Q E D)).
2.Так как новый Y не является пустым списком и Q не равно S, то
(MEMBER `Q `(Q E D)).
3.Так как новый Y не является пустым списком, но Q равно Q, то функ-
ция завершает работу и возвращает Y3: (Q E D).
·······································································
······················· 
Пример 2.2 ·······················
Предположим, что необходимо написать функцию sumall, которая имеет один аргумент N – целое положительное число и возвращает сумму всех целых чисел между нулем и этим числом.
Например (sumall 9) должно вернуть 45. Отметим два факта:
1.Если N=0, сумма чисел между нулем и N равна 0.
2.Если N>0, сумма чисел между нулем и N равна N плюс сумма чисел
между нулем и N-1.
Эти два факта переводятся непосредственно в определение функции:
(defun sumall (n)
(cond ((zerop n) 0)
(t (+ n (sumall (- n 1))))))
Производится проверка N: равно нулю или нет. Если значение N=0, то функция возвращает 0. В противном случае функция вызывает сама себя для вычисления суммы чисел между 0 и N-1 и добавляет N к этой сумме.
·······································································
2.2 Как работает рекурсивная функция
Посмотрим, как работает рекурсивная функция. Проследим за несколькими вызовами функции, описанной в примере 2.2.
Ясно, как работает (sumall 0). Функция возвращает 0. Эта ветвь в
32
cond называется терминальной (terminating), или завершающей, так как функция дает значение без рекурсивного вызова.
Если (sumall 1), то расчет идет по второй ветке, которая называется рекурсивной, так как идет вызов самой себя. В этом случае выполняется выражение (+ 1 (sumall 0)), и значение функции равно 1.
Если (sumall 2), то по рекурсивной ветке выполняется (+ 2 (sumall 1)) и функция возвращает 3.
Если значение аргумента равно 3, то
(sumall 3) вызывает (sumall 2) (sumall 1) вызывает (sumall 0). После того как (sumall 0) вернет 0,
(sumall 1) вернет 1, (sumall 2) вернет 3,
(sumall 3) (это вызов верхнего уровня) даст значение 6.
2.3 Правила записи рекурсивной функции
Рассмотренный выше простой случай иллюстрирует несколько правил в записи рекурсивной функции.
Правило 1. В рекурсивном определении существенен порядок следования условий. При определении порядка следования основным моментом является то, что сначала проверяются всевозможные условия окончания, а затем ситуации, требующие продолжения вычислений.
Правило 2. Терминальная ветвь необходима для окончания вызова. Без терминальной ветви рекурсивный вызов был бы бесконечным. Терминальная ветвь возвращает результат, который является базой для вычисления результатов рекурсивных вызовов.
Правило 3. После каждого вызова функцией самой себя мы должны приближаться к терминальной ветви. В нашем случае вызовы уменьшали N, и была гарантия, что на некотором шаге будет вызов (sumall 0). Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви.
Проследить вычисления в рекурсии чрезвычайно сложно. Очень трудно мысленно проследить за действием рекурсивных функций. Это практически невозможно для функций более сложных, чем sumall.
Таким образом мы должны уметь писать рекурсивные функции, без того чтобы представлять точно порядок вычисления.
33
При написании рекурсивной функции необходимо:
1.Планирование терминальной ветви. При написании рекурсивной функции мы должны решить, когда функция может вернуть значение без рекурсивного вызова.
2.Планирование рекурсивной ветви. В этом случае мы вызываем функцию рекурсивно с упрощенным аргументом и используем результат для расчета значения при текущем аргументе.
Таким образом, мы должны решить:
1.Как упрощать аргумент, приближая его шаг за шагом к конечному зна-
чению.
2.Кроме этого необходимо построить форму, называемую рекурсивным отношением, которая связывает правильное значение текущего вызова со зна-
чением рекурсивного вызова. В рассмотренном примере это (sumall N) и (sumall (– N 1)). Иногда просто найти это отношение, а если не получается, то надо выполнить следующую последовательность шагов:
•определить значение некоторого простого вызова функции и ее соответствующего рекурсивного вызова;
•определить соотношение между парой этих функций.
······················· 
Пример 2.3 ·······················
Определим функцию возведения в степень power. Она берет два численных аргумента M и N и вычисляет значение M в степени N.
Вначале составим рекурсивную таблицу.
Шаг 1. Завершение (терминальная ветвь) N=0 – аргумент, (power 2 0)=1 – значение функции.
Шаг 2. Рекурсивная ветвь – рекурсивные отношения между (power M N) и (power M (– N 1)).
Примеры рекурсии:
(power 5 3) ==> 125 (power 5 2) ==> 25 (power 3 1) ==> 3 (power 3 0 ) ==> 1
Характеристическое рекурсивное отношение (power M N) может быть получено из отношения (power M (– N 1) путем его умножения на M.
34
Полученная функция:
(defun power (m n)
(cond ((zerop n) 1)
(t (* m (power m (- n 1))))))
Логика и структура СDR рекурсии сходна с численной рекурсией.
······································································ .
······················· 
Пример 2.4 ·······················
Написать функцию list-sum, которая берет один аргумент Y – список чисел, и возвращает сумму этих чисел.
Последовательно упрощающимся аргументом в этом случае будет список. Упрощение списка (cdr Y). Последнее значение аргумента nil.
Составим рекурсивную таблицу для (list–sum Y).
Шаг 1. Завершение (терминальная ветвь) (list–sum nil)=0 – значе-
ние.
Шаг 2. Рекурсивная ветвь: рекурсивные отношения между выражениями
(list–sum Y) и (list-sum (cdr Y)). Примеры рекурсии:
(list-sum '(2 5 3)) ==> 10 (list-sum '(5 3)) ==> 8 (list-sum '(3)) ==> 3 (list-sum nil ) ==> 0
Характеристическое рекурсивное отношение (list–sum Y) может
быть получена из (list–sum (cdr Y)) сложением с (car Y). Текст функции:
(defun list-sum (Y)
(cond ((null Y) 0)
(t (+ (car Y) (list-sum (cdr Y))))))
·······································································
2.4 Рекурсия
с несколькими терминальными или рекурсивными ветвями
Несколько терминальных ветвей
Мы рассмотрели случай рекурсии с одной терминальной и одной рекурсивной ветвью. Однако в определении рекурсивной функции может быть не-
35
сколько терминальных ветвей. Две терминальные ветви будут в том случае, когда ведется поиск цели в последовательности значений, и мы желаем получить результат, как только цель найдена.
Ветвь 1. Цель найдена, и надо вернуть ответ. Ветвь 2. Цель не найдена, и элементов больше нет.
На рисунке 2.1 показан принцип построения функции с несколькими терминальными ветвями.
|
Функция |
|
|
Терминальная ветвь |
Рекурсивная ветвь |
||
Цель найдена |
Цель не найдена |
Ветвь 1 |
Ветвь 2 |
и нет элементов |
|
|
|
|
|
|
|
|
Выход |
|
|
Рис. 2.1 – Функция с несколькими терминальными ветвями |
|||
······················· 
Пример 2.5 ·······················
Необходимо написать функцию greaternum. Она имеет два аргумента: список чисел L и заданное число X. Функция возвращает первое число в списке, превышающее заданное. Если этого числа нет, возвращается заданное число.
Программа
(defun greaternum (lis num) (cond ((null lis) num)
((> (car lis) num) (car lis))
(t (greaternum (cdr lis) num))))
·······································································
·····························································
Порядок ветвей в рекурсивном определении существенен.
·····························································
36
Несколько рекурсивных ветвей
Несколько рекурсивных ветвей могут понадобиться, если функция обрабатывает все элементы в структуре, но использует некоторые элементы отлично от других. В этом случае составляются два рекурсивных отношения.
······················· 
Пример 2.6 ·······················
Необходимо написать функцию negnums, которая получает список чисел L и возвращает список, который содержит только отрицательные числа (0 положителен).
Шаг 1. Завершение (терминальная ветвь) (negnums nil)=nil.
Шаг 2. Рекурсивная ветвь: рекурсивные отношения между
(negnums l) и (negnums (cdr l)). Примеры рекурсии:
(negnums '(-5 3)) = (-5) (negnums '(3)) = nil
(negnums '(-5 3 -6 0 )) = (-5 -6) (negnums '(3 -6 0 )) = (-6)
Ситуация (car l ) < 0
Характеристическое рекурсивное отношение (negnums L) может быть получено из (negnums (cdr L)) следующим образом: (cons (car L) (negnums (cdr L)).
Ситуация (car l ) >= 0
Характеристическое рекурсивное отношение (negnums L) может быть получено из (negnums (cdr L)) через (negnums L)=(negnums (cdr L)).
Программа
(defun negnums (L)
(cond ((null L) nil)
((< (car L) 0) (cons (car L) (negnums (cdr L)))) (t (negnums (cdr L)))))
·······································································
·····························································
Минимальное значение k для заданного аргумента, при кото-
ром выполняется условие завершения, будем называть глубиной
рекурсии.
·····························································
37
······················· 
Пример 2.7 ·······················
Рассмотрим функцию SUM, которая суммирует все числа, содержащиеся в некотором произвольном выражении (будем рассматривать выражения, состоящие из любых атомов и списков). Определение функции можно записать так:
(DEFUN SUM (X)
(COND ((NUMBERP X) X)
((AТОМ X) 0)
(Т (+ (SUM (CAR X)) (SUM (CDR X))))))
Рассмотрим поэтапное вычисление следующего обращения к функции: (SUM '(A (3 5) . 7)). В теле функции будет вычисляться следующее выражение:
1. (+ (SUM (CAR '(A (3 5) . 7))) (SUM (CDR '(A (3 5) . 7)))
В результате вычисления CAR получаем следующее:
2. (+ (SUM A) (SUM (CDR '(A (3 5) . 7)))
Значением первого слагаемого становится 0. После этого вычисляется CDR, в результате чего получаем следующее:
3. (+ 0 (SUM '((3 5) . 7)))
Теперь рассматриваем список ((3 5) . 7):
4. (+ 0
(+ (SUM '(3 5)) (SUM (CDR '((3 5) . 7)))))
Далее порядок вычислений будет следующим:
5. (+ 0
(+ (+ (SUM '3) (SUM (CDR '(3 5)))) (SUM (CDR '((3 5) . 7)))))
6. (+ 0
(+ (+ 3 (SUM '(5)))
(SUM (CDR '((3 5) . 7)))))
7. (+ 0
(+ (+ 3 (+ 5 (SUM 'NIL))) (SUM (CDR '((3 5) . 7)))))
8. (+ 0 (+ (+3 (+ 5 0))
(SUM (CDR '((3 5) . 7)))))
9. (+ 0 (+ 8
(SUM '7)))
38
10. (+ 0
(+ 8 7))
После суммирования получается результат – 15. Для рассмотренного примера глубина рекурсии равна 4.
·······································································
2.5Вспомогательные функции над списками
Вэтом разделе мы рассмотрим ряд часто встречающихся вспомогательных функций. Большинство из этих функций обычно являются встроенными. Если же в какой-то реализации Лиспа отсутствует необходимая функция, то можно воспользоваться приводимым ниже определением.
Функция APPEND
(APPEND x y). Это обычная функция. Значением функции является список, получающийся в результате конкатенации (соединения) списков x и y. Определить функцию можно так:
(DEFUN APPEND (X Y) (COND ((ATOM X) Y)
(T (CONS (CAR X) (APPEND (CDR X) Y)))))
Примеры обращения к функции:
(APPEND '(A B) '(C (1) D)) ==> (A B C (1) D) (APPEND '(1 2 3) '(7 8)) ==> (1 2 3 7 8)
Ниже приведен пример, иллюстрирующий разницу работы трех функ-
ций – LIST, CONS и APPEND.
(LIST `(1 2) `(3 4)) ==> ((1 2) (3 4)) (CONS `(1 2) `(3 4)) ==> ((1 2) 3 4) (APPEND `(1 2) `(3 4)) ==> (1 2 3 4)
Таким образом, отличие объединяющих функций LIST, CONS и APPEND
заключается в следующем:
•CONS всегда берет два аргумента и помещает первый в начало второго;
•LIST берет один или больше аргументов и образует список, помещая аргументы в скобки;
•APPEND образует новый список, убирая скобки вокруг аргументов и
помещая их в один список.
На самом деле, на внутреннем уровне представления списков тоже существуют различия в работе трех указанных функций. Работа функций CONS и
39
LIST на внутреннем уровне была рассмотрена ранее. Покажем теперь работу функции APPEND.
Рассмотрим следующую последовательность действий:
(setq first '(a b)) ==> (a b) (setq second '(c d)) ==> (c d)
(setq both (append first second)) ==> (a b c d)
Эти действия показывает диаграмма, приведенная на рисунке 2.2.
До операции |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
FIRST |
|
|
|
|
|
SECOND |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
\ |
|
|
|
|
|
|
|
|
|
|
\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
A |
B |
|
|
|
|
C |
D |
||||||||||||
После |
|
|
|
|
|
|
Надо |
заменить |
|
|
|
||||||||||
|
|
|
|
|
|
|
|||||||||||||||
BOTH |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Копия
Рис. 2.2 – Работа функции APPEND на внутреннем уровне
APPEND создает копии всех списочных ячеек для каждого элемента во всех аргументах, исключая последний аргумент.
CONS создает только одну списочную ячейку.
LIST создает списочную ячейку для каждого элемента функции.
Если складывают два списка в 1 000 и 1 элемент с помощью APPEND, то будет создано 1 000 копий списочных ячеек, вместо того чтобы исправить один указатель.
LIST в этом случае создаст только две списочных ячейки (два списка – два элемента).
Функция REVAPPEND
(REVAPPEND x у). Это обычная функция. Она выполняет конкатенацию перевернутого списка x со списком у.
Ее определение может быть таким:
(DEFUN REVAPPEND (X Y) (COND ((ATOM X) Y)
(T (REVAPPEND (CDR X) (CONS (CAR X) Y)))))
Примеры использования:
(REVAPPEND '(A (B C) D) '(1 2)) ==> (D (В С) А 1 2) (REVAPPEND '(А В С) '(2)) ==> (С В А 2)
40
(REVAPPEND '(ONE TWO) ()) ==> (TWO ONE)
Функция REVERSE
(REVERSE x). Это обычная функция. Значением функции является список, полученный из элементов списка x, расположенных в обратном порядке. Необходимо отметить, что данная функция реверсирует только верхний уровень списка.
Определение функции:
(DEFUN REVERSE (X)
(COND ((NULL X) NIL)
(T (APPEND (REVERSE (CDR X)) (LIST (CAR X))))))
С использованием функции REVAPPEND функцию REVERSE можно определить значительно короче:
(DEFUN REVERSE (X)
(REVAPPEND X NIL))
Пример использования:
(REVERSE '(10 (А В) 20)) ==> (20 (А В) 10)
Функция NTH
(NTH i x). Это обычная функция. Значением функции является i-й элемент списка x. Элементы нумеруются начиная с нуля. Ее можно определить следующим образом:
(DEFUN NTH (I L)
(COND ((ATOM L) NIL) ((ZEROP I) (CAR L))
(T (NTH (- I 1) (CDR L)))))
Примеры использования:
(NTH 1 '(1 2 3)) ==> 2
(NTH 3 '(А В С (D E))) ==> (D E) (NTH 0 '(А В С)) ==> A
Функция NTHCDR
(NTHCDR i x). Эта функция обычная. Значением ее является список x без i начальных элементов. Определение функции может быть таким:
(DEFUN NTHCDR (I L) (COND ((NULL L) NIL)
((ZEROP I) L)
(T (NTHCDR (- I 1) (CDR L)))))
Примеры:
(NTHCDR 0 '(1 2 3)) ==> (1 2 3) (NTHCDR 2 '(1 2 3)) ==> (3)