Композиции функционалов, фильтры, редукции
Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций. Композиции функционалов позволяют создавать и более мощные построения, достаточно ясные, но требующие некоторого внимания.
Декартово произведение хочется получить определением вида:
(defun decart (x y) (map-el #' (lambda (i) (map-el #' (lambda (j) (list i j)) y) ) x) )
Пример 4.10.
Но результат вызова
(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 (пример 4.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))
Пример 4.11.
Тогда по аналогии можно построить определение функционала map-ap:
(defun map-ap (fn ll) (cond (ll (append (funcall 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)
Пример 4.12.
Рассмотрим еще один типичный вариант применения функционалов. Представим, что нас интересуют некие интегральные характеристики результатов, полученных при отображении, например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В таком случае говорят о свертке результата или его редукции. Редукция заключается в сведении множества элементов к одному элементу, в вычислении которого задействованы все элементы множества.
Подсчитать сумму элементов заданного списка.
(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) )
(sum-el '(1 2 3 4) ) ; = 10
Пример 4.13.
Перестроим такое определение, чтобы вместо <+> можно было использовать произвольную бинарную функцию:
(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 ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.
Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.