Введение в программирование на Лиспе

Отображения и функционалы

Разбить на страницы
Показывать лекцию целиком

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

При определении отображений прежде всего должны быть ясны следующие вопросы:

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

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

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

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

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

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

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

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

    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"

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

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

    Базовые фукнции над числами
    (= Число … ) Истина, если разница между любыми двумя аргументами равна нулю
    (/= Число … ) Истина, если никакие два аргумента не равны между собой
    (> Число … ) Истина, если каждый аргумент превышает прешественника
    (< Число … ) Истина, если каждый аргумент меньше прешественника
    (<= Число … ) Истина, если каждый аргумент меньше или равен прешественнику
    (>= Число … ) Истина, если каждый аргумент превышает или равен прешественнику
    (* Число … ) Произведение произвольного числа аргументов. 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 )
    (defun 1st (xl)                  ; "головы" элементов = CAR
     (cond                       ; пока список не пуст
        (xl (cons (caar xl)      ; выбираем CAR от его головы
                  (1st (cdr xl)) ; и переходим к остальным,
)    )  )   )                    ; собирая результаты в список

(1st '((один два )(one two )(1 2 )) )  ; = (один one 1)
    (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 )

    Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию map-el, в определении которой имена " car ", " 1+ " и " length " могут быть заданы как значения параметра 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

    Построить список квадратов чисел, используя функцию 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))
)    )  )   )
    (defun tuple (x) (cons x x))
(tuple 3)             ; = (3 . 3)
(tuple 'a)       ; = (a . a)
(tuple '(Ха))    
     ; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же!

    Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:

    (defun duble (xl) (map-el #'tuple xl))   
            ; дублирование элементов 
(duble '(1(a)()));=((1.1)((a)a)(()))

    Немногим сложнее организовать покомпонентную обработку двух списков.

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

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

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

    (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 (funcall (car fl) el)
             ; применяем очередную функцию 
             ; ко второму аргументу
                   (mapf (cdr fl) el) 
             ; и переходим к остальным функциям, 
) ) ) )     ; собирая их результаты в общий список

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

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

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

    Определения в примерах 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))

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

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

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

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

    (defun decart (x y)
   (map-el #'(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)))

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

    ((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))

    Тогда по аналогии можно построить определение фукнционала 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)

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

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

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

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

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

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

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

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

    Выводы:

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

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

    При определении отображений прежде всего должны быть ясны следующие вопросы:

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

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

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

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

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

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

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

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

    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"

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

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

    Базовые фукнции над числами
    (= Число … ) Истина, если разница между любыми двумя аргументами равна нулю
    (/= Число … ) Истина, если никакие два аргумента не равны между собой
    (> Число … ) Истина, если каждый аргумент превышает прешественника
    (< Число … ) Истина, если каждый аргумент меньше прешественника
    (<= Число … ) Истина, если каждый аргумент меньше или равен прешественнику
    (>= Число … ) Истина, если каждый аргумент превышает или равен прешественнику
    (* Число … ) Произведение произвольного числа аргументов. 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 )
    (defun 1st (xl)                  ; "головы" элементов = CAR
     (cond                       ; пока список не пуст
        (xl (cons (caar xl)      ; выбираем CAR от его головы
                  (1st (cdr xl)) ; и переходим к остальным,
)    )  )   )                    ; собирая результаты в список

(1st '((один два )(one two )(1 2 )) )  ; = (один one 1)
    (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 )

    Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию map-el, в определении которой имена " car ", " 1+ " и " length " могут быть заданы как значения параметра 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

    Построить список квадратов чисел, используя функцию 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))
)    )  )   )
    (defun tuple (x) (cons x x))
(tuple 3)             ; = (3 . 3)
(tuple 'a)       ; = (a . a)
(tuple '(Ха))    
     ; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же!

    Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:

    (defun duble (xl) (map-el #'tuple xl))   
            ; дублирование элементов 
(duble '(1(a)()));=((1.1)((a)a)(()))

    Немногим сложнее организовать покомпонентную обработку двух списков.

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

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

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

    (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 (funcall (car fl) el)
             ; применяем очередную функцию 
             ; ко второму аргументу
                   (mapf (cdr fl) el) 
             ; и переходим к остальным функциям, 
) ) ) )     ; собирая их результаты в общий список

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

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

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

    Определения в примерах 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))

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

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

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

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

    (defun decart (x y)
   (map-el #'(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)))

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

    ((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))

    Тогда по аналогии можно построить определение фукнционала 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)

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

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

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

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

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

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

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

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

    Выводы:

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