Безымянные функции

Определения в примерах 4 и 5 не вполне удобны по следующим причинам:

В определениях целевых функций duble и sqwure встречаются имена специально определенных вспомогательных функций.Формально эти функции независимы, значит программист должен отвечать за их наличие при использовании целевых функций на протяжении всего жизненного цикла программы, что трудно гарантировать.Вероятно, имя вспомогательной функции будет использоваться ровно один раз - в определении целевой функции.

С одной стороны последнее противоречит пониманию смысла именования как техники, обеспечивающей неоднократность применения поименованного объекта. С другой стороны придумывать хорошие, долго сохраняющие понятность и соответствие цели, имена - задача нетривиальная.

Учитывая это, было бы удобнее вспомогательные определения вкладывать непосредственно в определения целевых функций и обходиться при этом вообще без имен. Конструктор функций lambda обеспечивает такой стиль построения определений. Этот конструктор любое выражение expr превращает в функцию с заданным списком аргументов (x1 ... xK) в форме так называемых lambda-выражений:

( lambda (x1 ... xK) expr )

Имени такая функций не имеет, поэтому может быть применена лишь непосредственно. Defun использует этот конструктор, но, кроме того, дает функциям имена.

(defun sqware (xl)(map-el(lambda(x)(* x x))xl)) (defun duble (xl)(map-el(lambda(x)(cons x x))xl))

Пример 7.9. Определение функций duble и sqwure из примеров 4 и 5 без использования имен и вспомогательных функций: (html, txt)

Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.

Числа и строки

Любую информацию можно представить символьными выражениями. В качестве основных видов символьных выражений выбраны списки и атомы. Атом - неделимое данное, представляющее информацию произвольной природы. Но во многих случаях знание природы информации дает более четкое понимание особенностей изучаемых механизмов.

Программирование работы с числами и строками – привычная, хорошо освоенная область информационной обработки, удобная для оценки преимуществ использования функционалов. Опуская технические подробности, просто отметим, что числа и строки рассматриваются как самоопределимые атомы, смысл которых не требует никакого ассоциирования, он понятен просто по виду записи. Например, натуральные числа записываются без особенностей и могут быть почти произвольной длины:

1 -123 9876543210000000000000123456789

Можно работать с дробными и вещественными числами:

8/12 ;= 2/3 3.1415926

Строки заключаются в обычные двойные кавычки:

"строка любой длины, из произвольных символов, включая все что угодно"

Со строками можно при необходимости работать посимвольно, хотя они рассматриваются как атомы.

(string-equal "строка 1" " строка1");=Nil (ATOM "a+b-c") ;= T (char "стр1" 4 ) ;= "1"

Список - составное данное, первый элемент которого может рассматриваться как функция, применяемая к остальным элементам, также представленным как символьные выражения.

Это относится и к операциям над числами и строками.

Большинство операций над числами при префиксной записи естественно рассматривать как мультиоперации от произвольного числа аргументов.

(+ 1 2 3 4 5 6) ;= 21 (- 12 6 3) ;= 3 (/ 3 5) ;= 3/5

Любое данное можно превратить в константу, поставив перед ним "'" апостроф. Это эквивалентно записи со специальной функцией "QUOTE". Для чисел и строк в этом нет необходимости, но это не запрещено:

'1 ;= 1 '"abc" ;= "abc"

Отказ от барьера между представлениями функций и значений дает возможность символьные выражения использовать как для изображения заданных значений, включая любые структуры над числами и строками, так и для определения функций, обрабатывающих любые данные. (Напоминаем, что определение функции - данное.)

Функционалы - это функции, которые используют в качестве аргументов или результатов другие функции. При построении функционалов переменные могут выполнять роль имен функций, определения которых находятся во внешних формулах, использующих функционалы.

Таблица 7.1. Базовые фукнции над числами

(= Число … )	Истина, если разница между любыми двумя аргументами равна нулю
(/= Число … )	Истина, если никакие два аргумента не равны между собой
(> Число … )	Истина, если каждый аргумент превышает прешественника
(< Число … )	Истина, если каждый аргумент меньше прешественника
(<= Число … )	Истина, если каждый аргумент меньше или равен прешественнику
(>= Число … )	Истина, если каждый аргумент превышает или равен прешественнику
(* Число … )	Произведение произвольного числа аргументов. 1 при их отсутствии.
(+ Число … )	Сумма произвольного числа аргументов. 0 при их отсутствии.
(- Число … )	Эквивалентно расстановке минусов между аргументами, т.е. (- a b c ) = a – b – c
(/ Число … )	Первое число делится на произведение остальных, среди которых не должно быть нуля.
(1+ Число )	( + Число 1)
(1- Число )	( - Число 1)
(Boole Операция Целое1 Целое2 )	Вычисляет результат применеия побитовой Операции к двум Целым.
(Gcd Число …)	Наибольший общий делитель. Ноль без аргументов.
(Lcm Число … )	Наименьшее общее произведение, 1 при отсутствии аргументов.
(min Число …)
(max Число …)

Функционалы

Рассмотрим технику использования функционалов и наметим, как от простых задач перейти к более сложным.

(defun next (xl) ; Следующие числа: (cond ; пока список не пуст (xl (cons (1+ (car xl)) ; прибавляем 1 к его голове (next (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список

(next '(1 2 5 )) ; = (2 3 6 )

Пример 7.1. Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в список. (html, txt)

(defun 1st (xl) ; "головы" элементов = CAR (cond ; пока список не пуст (xl (cons (caar xl) ; выбираем CAR от его головы (1st (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список

(1st '((один два )(one two )(1 2 )) ) ; = (один one 1)

Пример 7.2. Построить список из "голов" элементов списка (html, txt)

(defun lens (xl) ; Длины элементов (cond ; Пока список не пуст (xl (cons (length (car xl)); вычисляем длину его головы (lens (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список

(lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ) ; = (2 0 4 3 )

Пример 7.3. Выяснить длины элементов списка (html, txt)

Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию map-el, в определении которой имена "car", "1+" и "lenth" могут быть заданы как значения параметра fn:

(defun map-el (fn xl) ; Поэлементное преобразование XL ; с помощью функции FN. (cond ; Пока XL не пуст, (xl (cons (funcall fn (car xl) ) ; применяем FN как функцию к голове XL

(map-el fn (cdr xl)) ; и переходим к продолжению списка, ) ) ) ) ; собирая результаты в новый список.

Примечание: funcall – это аналог apply, не требующий заключения аргументов в общий список:

(APPLY (DEFUN Пара (x y) (CONS x y)) (QUOTE (A (B C))));=(A B C)

(FUNCALL (DEFUN Пара (x y) (CONS x y)) (QUOTE A) (QUOTE (B C)));=(A B C)

Эффект функций next, 1st и lens можно получить выражениями:

(map-el #'1+ xl) ;следующие числа (map-el #'car xl) ;"головы" элементов = CAR

#’ x ;= (FUNCTION x) - сокращенное обозначение функции-значения соответственно.

(map-el #'length xl) ; Длины элементов

(map-el #'1+ '(1 2 5 )) ; = (2 3 6 ) (map-el #'car ' ((один два)(one two)(1 2)));=(один one 1) (map-el #'length '((1 2)()(a b c d)(1(a b c d)3))) ; = (2 0 4 3 )

Эти определения функций формально эквивалентны ранее приведенным – они сохраняют отношение между аргументами и результатами.

Все три примера можно решить с помощью таких определяющих выражений:

(defun next (xl) (map-el #'1+ xl )) ; Очередные числа: (defun 1st (xl) (map-el #'car xl )) ; "головы" элементов = CAR (defun lens (xl) (map-el #'length xl )) ; Длины элементов

Параметром функционала может быть любая вспомогательная функция.

(defun sqw (x) (* x x)); Возведение числа в квадрат (sqw 3) ; = 9

Пример 7.4. Пусть дана вспомогательная функция sqw, возводящая числа в квадрат (html, txt)

Построить список квадратов чисел, используя функцию sqw:

(defun sqware (xl) ; ; Возведение списка чисел в квадрат (cond ; Пока аргумент не пуст, (xl (cons (sqw (car xl)) ; применяем sqw к его голове (sqware (cdr xl)) ; и переходим к хвосту списка, ) ) ) ) ; собирая результаты в список

(sqware '(1 2 5 7 )); = (1 4 25 49 )

Можно использовать map-el:

(defun sqware (xl) (map-el #'sqw xl))

Ниже приведено определение функции sqware- без вспомогательной функции, выполняющее умножение непосредственно. Оно влечет двойное вычисление (CAR xl), т.е. такая техника не вполне эффективна:

(defun sqware- (xl) (cond (xl (cons (* (car xl) (car xl) ); квадрат головы ; вычислять приходится дважды (sqware- (cdr xl)) ) ) ) )

(pair '(один два two three) '(1 2 два три)) ; = ((один . 1)(два . 2)(two два )(three три ))

Пример 7.6. Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:

(defun map-comp (fn al vl) ; fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (fn (car al) (car vl)) ; Вызов данного FN как функции (map-comp (cdr al) (cdr vl)) ) ) ) )

Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:

Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:

(map-comp #'+ '(1 2 3) '(4 6 9)) ; = (5 8 12 ) - Суммы (map-comp #'* '(1 2 3) '(4 6 9)) ; = (4 12 27)-Произведения (map-comp #'cons '(1 2 3) '(4 6 9)) ; = ((1.4)(2.6)(3.9))-Пары (map-comp #'eq '(4 2 3 ) '(4 6 9)) ; = (T NIL NIL)-Сравнения

Достаточно уяснить, что надо делать с элементами списка, остальное делает отображающий функционал map-comp.

(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons ((car fl) el ) ; применяем очередную функцию ; ко второму аргументу (mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) )) ; собирая их результаты в общий список

(mapf '(length car cdr)'(a b c d));=(4 a(b c d))

Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.

Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками.

Композиции функционалов, фильтры, редукции

Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций.

Композиции функционалов позволяют порождать и более мощные построения, достаточно ясные, но требующие некоторого внимания.

(defun decart (x y) (map-el #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) )

Пример 7.10. Декартово произведение хочется получить определением вида: (html, txt)

Но результат вызова

(decart '(a s d) '( e r t))

дает

(((A E)(A R)(A T))((S E)(S R)(S T))((D E)(D R)(D T)))

вместо ожидаемого

((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))

Дело в том, что функционал map-el, как и map-comp (пример 7), собирает результаты отображающей функции в общий список с помощью операции cons так, что каждый результат функции образует отдельный элемент.

А по смыслу задачи требуется, чтобы список был одноуровневым.

Посмотрим, что получится, если вместо cons при сборе результатов воспользоваться функцией append.

(defun list-ap (ll) (cond (ll (append (car ll) (list-ap (cdr ll) ) ) ) ) )

(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))

Пример 7.11. Пусть дан список списков. Нужно их все сцепить в один общий список. (html, txt)

Тогда по аналогии можно построить определение фукнционала map-ap:

(defun map-ap (fn ll) (cond (ll (append (fn (car ll) ) (map-ap fn (cdr ll) ) ) ) ) )

(map-ap 'cdr '((1 2 3 4)(2 4 6 8)( 3 6 9 12))) ; = (2 3 4 4 6 8 6 9 12)

Следовательно, интересующая нас форма результата может быть получена:

(defun decart (x y) (map-ap #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) ) (decart '(a s d) '( e r t)) ;=((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))

Соединение результатов отображения с помощью append обладает еще одним полезным свойством: при таком сцеплении исчезают вхождения пустых списков в результат. А в Лиспе пустой список используется как ложное значение, следовательно такая схема отображения пригодна для организации фильтров. Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.

(defun heads (xl) (map-ap #'(lambda (x)(cond (x (cons (car x) NIL)))) ; временно голова размещается в список, ; чтобы потом списки сцепить xl ) ) (heads '((1 2)()(3 4)()(5 6))) ;=(1 3 5)

Пример 7.12. Построить список голов непустых списков можно следующим образом: (html, txt)

Рассмотрим еще один типичный вариант применения функционалов. Представим, что нас интересуют некие интегральные характеристики результатов, полученных при отображении, например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В таком случае говорят о свертке результата или его редукции. Редукция заключается в сведении множества элементов к одному элементу, в вычислении которого задействованы все элементы множества.

(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) )

(sum-el '(1 2 3 4 ) ) ; = 10

Пример 7.13. Подсчитать сумму элементов заданного списка. (html, txt)

Перестроим определение, чтобы вместо "+" можно было использовать произвольную бинарную функцию:

(defun red-el (fn xl) (cond ((null xl) 0) (xl (fn (car xl) (red-el fn (cdr xl) ) )))) (red-el '+ '(1 2 3 4 ) ) ; = 10

В какой-то мере map-ap ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.

Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.

Таблица 7.2. Clisp: встроенные функционалы

(Mapc Функция Список … )	Отображает ряд списков с помощью Функции. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент.
(Mapcan Функция Список … )	Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc.
(Mapcar Функция Список … )	Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции.
(Mapcon Функция Список … )	Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc.
(Mapl Функция Список … )	Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент.
( Maplist Функция Список … )	Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции.

Для каждого числа из заданного

Пример 7.1. Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в список.

Закрыть окно

пока список не

(defun next (xl) ; Следующие числа:
(cond ; пока список не пуст
(xl (cons (1+ (car xl)) ; прибавляем 1 к его голове
(next (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(next '(1 2 5 )) ; = (2 3 6 )

выбираем CAR от его головы

Пример 7.2. Построить список из "голов" элементов списка

Закрыть окно

выбираем CAR от его

(defun 1st (xl) ; "головы" элементов = CAR
(cond ; пока список не пуст
(xl (cons (caar xl) ; выбираем CAR от его головы
(1st (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(1st '((один два )(one two )(1 2 )) ) ; = (один one 1)

Пока список не пуст

Пример 7.3. Выяснить длины элементов списка

Закрыть окно

Пока список не

(defun lens (xl) ; Длины элементов
(cond ; Пока список не пуст
(xl (cons (length (car xl)); вычисляем длину его головы
(lens (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ) ; = (2 0 4 3 )

Пусть дана вспомогательная функция sqw,

(defun sqw (x) (* x x)); Возведение числа в квадрат (sqw 3) ; = 9

Пример 7.4. Пусть дана вспомогательная функция sqw, возводящая числа в квадрат

Закрыть окно

defun sqw

( defun sqw (x) (* x x)); Возведение числа в квадрат
(sqw 3) ; = 9

Пусть дана вспомогательная функция tuple,

(defun tuple (x) (cons x x)) (tuple 3) ; = (3 . 3) (tuple 'a) ; = (a . a) (tuple '(Ха)) ; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же!

Пример 7.5. Пусть дана вспомогательная функция tuple, превращающая любое данное в пару:

Закрыть окно

defun tuple

( defun tuple (x) (cons x x))
(tuple 3) ; = (3 . 3)
(tuple 'a) ; = (a . a)
(tuple '(Ха))
; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же!

то CDR будет давать NIL

(defun pairl (al vl); Ассоциативный список (cond ; Пока AL не пуст, (al (cons (cons (car al) (car vl)) ; строим пары из "голов". (pairl (cdr al) (cdr vl)) ; Если VL исчерпается, ; то CDR будет давать NIL ) ) ) )
(pair '(один два two three) '(1 2 два три)) ; = ((один . 1)(два . 2)(two два )(three три ))

Пример 7.6. Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:

Закрыть окно

то CDR будет давать

(defun pairl (al vl); Ассоциативный список
(cond ; Пока AL не пуст,
(al (cons (cons (car al) (car vl))
; строим пары из "голов".
(pairl (cdr al) (cdr vl))
; Если VL исчерпается,
; то CDR будет давать NIL
) ) ) )
(pair '(один два two three) '(1 2 два три))
; = ((один . 1)(два . 2)(two два )(three три ))

Вызов данного FN как функции

(defun map-comp (fn al vl) ; fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (fn (car al) (car vl)) ; Вызов данного FN как функции (map-comp (cdr al) (cdr vl)) ) ) ) )

Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:

Закрыть окно

к соотвественным элементам AL

(defun map-comp (fn al vl) ; fn покомпонентно применить
; к соотвественным элементам AL и VL
(cond
(xl (cons (fn (car al) (car vl))
; Вызов данного FN как функции
(map-comp (cdr al) (cdr vl))
) ) ) )

Пока первый аргумент не пуст,

(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons ((car fl) el ) ; применяем очередную функцию ; ко второму аргументу (mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) )) ; собирая их результаты в общий список
(mapf '(length car cdr)'(a b c d));=(4 a(b c d))

Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.

Закрыть окно

Пока первый аргумент не

(defun mapf (fl el)
(cond ; Пока первый аргумент не пуст,
(fl (cons ((car fl) el )
; применяем очередную функцию
; ко второму аргументу
(mapf (cdr fl) el)
; и переходим к остальным функциям,
) ) )) ; собирая их результаты в общий список
(mapf '(length car cdr)'(a b c d));=(4 a(b c d))

и sqwure из примеров

(defun sqware (xl)(map-el(lambda(x)(* x x))xl)) (defun duble (xl)(map-el(lambda(x)(cons x x))xl))

Пример 7.9. Определение функций duble и sqwure из примеров 4 и 5 без использования имен и вспомогательных функций:

Закрыть окно

defun sqware

( defun sqware (xl)(map-el(lambda(x)(* x x))xl))
(defun duble (xl)(map-el(lambda(x)(cons x x))xl))

Декартово произведение хочется получить определением

(defun decart (x y) (map-el #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) )

Пример 7.10. Декартово произведение хочется получить определением вида:

Закрыть окно

defun decart

( defun decart (x y)
(map-el #'(lambda (i)
(map-el #'(lambda (j) (list i j))
y)
) x) )

Пусть дан список списков. Нужно

(defun list-ap (ll) (cond (ll (append (car ll) (list-ap (cdr ll) ) ) ) ) )
(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))

Пример 7.11. Пусть дан список списков. Нужно их все сцепить в один общий список.

Закрыть окно

cdr ll)

(defun list-ap (ll)
(cond
(ll (append (car ll)
(list-ap ( cdr ll) )
) ) ) )
(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))

чтобы потом списки сцепить xl

Пример 7.12. Построить список голов непустых списков можно следующим образом:

Закрыть окно

временно голова размещается

Подсчитать сумму элементов заданного

(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) )
(sum-el '(1 2 3 4 ) ) ; = 10

Пример 7.13. Подсчитать сумму элементов заданного списка.

Закрыть окно

null xl)

(defun sum-el ( xl)
(cond (( null xl) 0)
(xl (+ (car xl)
(sum-el (cdr xl) )
) ) ) )
(sum-el '(1 2 3 4 ) ) ; = 10

Отображающие функционалы позволяют строить программы

Отображающие функционалы позволяют строить программы из крупных действий.Функционалы обеспечивают гибкость отображений.Определение функции может совсем не зависить от конкретных имен.С помощью функционалов можно управлять выбором формы результатов.Параметром функционала может быть любая функция, преобразующая элементы структуры.Функционалы позволяют формировать серии функций от общих данных.Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.