Композиции функционалов, фильтры, редукции
Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций.
Композиции функционалов позволяют порождать и более мощные построения, достаточно ясные, но требующие некоторого внимания.
(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 ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.
Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.
| (Mapc Функция Список … ) | Отображает ряд списков с помощью Функции. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент. |
| (Mapcan Функция Список … ) | Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc. |
| (Mapcar Функция Список … ) | Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции. |
| (Mapcon Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc. |
| (Mapl Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент. |
| ( Maplist Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции. |
