3.11 Сопоставление с образцом

Часто возникает задача сопоставления символьного факта и образца.

Выделим два понятия – образец и факт. Часто факт называют образом или данными (это то, что дано). Будем представлять образец и факт, как список атомов.

Примеры фактов:

(цвет яблоко красный)

(стол поддерживает блок12)

Образцы отличаются от атомов применением условных обозначений в виде символов * и &.

Тогда имеем:

(цвет * красный)

(& красный)

Символу * можно поставить в соответствие любой атом из факта, находящийся на том же месте , но только один;

Символу & можно поставить в соответствие один или несколько элементов из факта, в том числе и пустой элемент.

Общий алгоритм сопоставления с образцом, когда образец и факт – линейные списки, образец может содержать & и *.

ОБРАЗЕЦ сопоставим с ФАКТОМ при следующих условиях (здесь знак :=: обозначает сопоставимость); все пункты алгоритма связаны между собой связкой “или”

1)IF (ОБРАЗЕЦ=NIL) AND (ФАКТ=NIL), то ОБРАЗЕЦ=ФАКТ

OR

2)IF (ОБРАЗЕЦ<>NIL) AND ((CAR ОБРАЗЕЦ)=&) AND

(ФАКТ=NIL),то (CDR ОБРАЗЕЦ)=NIL

OR

3)IF (ОБРАЗЕЦ<>NIL) AND (ФАКТ<>NIL) AND

((CAR ОБРАЗЕЦ)=(CAR ФАКТ)) AND

((CDR ОБРАЗЕЦ):=:(CDR ФАКТ)),то

ОБРАЗЕЦ и ФАКТ сопоставимы

OR

4)IF (ОБРАЗЕЦ<>NIL) AND (ФАКТ<>NIL) AND ((CAR ОБРАЗЕЦ)=*)

AND ((CDR ОБРАЗЕЦ):=:(CDR ФАКТ)), то

ОБРАЗЕЦ и ФАКТ сопоставимы

OR

5)IF (ОБРАЗЕЦ<>NIL) AND (ФАКТ<>NIL) AND ((CAR ОБРАЗЕЦ)=&)

AND ((CDR ОБРАЗЕЦ):=:ФАКТ), то

ОБРАЗЕЦ и ФАКТ сопоставимы

OR

6)IF (ОБРАЗЕЦ<>NIL) AND (ФАКТ<>NIL) AND ((CAR ОБРАЗЕЦ)=&)

AND (ОБРАЗЕЦ:=:(CDR ФАКТ), то

ОБРАЗЕЦ и ФАКТ сопоставимы

Пусть требуется выяснить, используя правила, сопоставимы ли

(&, X) :=: (A B X)

1)(x):=:(a b x)- применяем п.5, NIL, goto п.6.

2)(& x):=:(b x)- п.5.

3)(x):=:(b x)- NIL, goto п.6.

4)(& x):=:(x)- goto п.5.

5)(x):=:(x)- п.3, УРА!

3.11.1 Функции Mapcad, Apply и Funcall

Функция Mapcad используется, когда одна и та же операция используется для одного и того же списка.

Пусть необходимо прибавить 1-цу ко все элементам списка.

(Mapcad ‘Add 1 ‘(2 3 4))  (3 4 5)

или может быть

( Mapcad ‘Egual ‘(1 2 3) ‘(3 2 1))  (nil t nil)

для Egual необходимо 2 аргумента

Функция Apply тоже вызывает функцию, но аргументы ей передаются как список

(Setq L '(1 2 3))

Тогда, если записать

(+L)  error

(Apply '+L) 6

применяет '+' ко всем элементам списка.

Funcall работает аналогично Apply, но аргументы передаются не списками, а по отдельности.

(Funcall '+2 3) 5

Пусть необходимо подсчитать количество атомов в списке:

(Times X (SQR Y))

Функцию можно задать следующим образом:

(Defun Fullength (X)

(Cond ((Null X) 0)

((Atom X) 1)

(T (Apply '+(Mapcar 'Fullength X)))

))

Рассмотрим как выполняется эта функция:

(Times X (SQR Y))

В итоге сформировав список (1 1) и применяя функцию '+', получаем 2; вызвав еще раз рекурсию складываем 1+1+24, т.е. в списке 4 атома.

Подсчитаем количество вложенности списка

(Defun Depth (X)

(Cond ((Null X) 1)

((Atom X) 0)

(T (Add1 (Apply 'Max(Mapcar 'Depth X)))

))

Рассмотрим работу функции

(Times X (SQR Y)) 2

Times

На самом верхнем уровне получаем список (0 0 1), прибавив 1 2. Применив max  2. Т.е. уровень вложенности  2.