Основы функционального программирования

Функционалы - общее понятие


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

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

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

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

Пример 4.1.

Построить список из <голов> элементов списка

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

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

Пример 4.2.

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

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

Пример 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)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список



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

(map-el #'1+ xl) ; Следующие числа: (map-el #'car xl) ; "головы" элементов = CAR (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)) ; Длины элементов

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

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

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

Пример 4.4.

Построить список квадратов чисел, используя функцию 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)) ) ) ) )

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

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

Пример 4.5.

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

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



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

Пример 4.6.

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

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

Пример 4.7.

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

(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.8.

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


Содержание раздела