1. Функциональное программирование. Основы Лиспа

Вид материала

Документы

Содержание Применяющие функционалы Функционал APPLY Предположим мы хотим объединить в один список несколько вложенных списков, т.е. из Пример: Определим функцию, которая рассчитывает среднее списка чисел Часто apply используют вместе c марсаr. Можно определить более сложную функцию countatom, которая считает элементы-атомы в любом списке. Функционал FUNCALL Здесь fn - функция с n aргументами. Эта функция имеет вид Встроенные функционалы Лямбда выражения Композиции функционалов, фильтры, редукции Сцепление результатов отображения Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты Выводы по применимости функционалов

Подобный материал:

• Рабочая программа по курсу "Функциональное программирование" Специальность, 144.38kb.
• Федеральное агентство по образованию, 124.95kb.
• В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
• Петербургский Гуманитарный Университет Профсоюзов (СПбгуп), с-петербург учебный курс, 20.72kb.
• Программа дисциплины Математическое программирование Семестры, 10.84kb.
• Методические указания и задания к курсовому проекту по дисциплине «Функциональное, 73.42kb.
• Программа дисциплины Функциональное программирование и интеллектуальные системы для, 148.26kb.
• Методические рекомендации для студентов по изучению курса «Функциональное программирование», 49.76kb.
• Рабочая программа по дисциплине "Функциональное и логическое программирование, 152.21kb.
• Программа элективного курса «Алгоритмизация и программирование», 95.38kb.

^

Применяющие функционалы

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

^

Функционал APPLY

Предположим мы хотим объединить в один список несколько вложенных списков, т.е. из

((a b c) (d e f) (k l))

получить

(a b c d e f k l).

Для этой задачи используем функцию apply, которая имеет два аргумента: имя функции и список, и применяет названную функцию к элементам списка, как к аргументам функции.

^

Пример: Определим функцию, которая рассчитывает среднее списка чисел

(defun list-mean (x)

(/ (apply `+ x) (length x))

)


(list-mean `(1 2 3 4))

; 2.5
^

Часто apply используют вместе c марсаr.

Пример: найти общее число элемент в списках

(defun countall (lis)

(apply `+ (mapcar ` length lis))

)


(countall `((a b c) (d e f) (k l)))

; 8

^

Можно определить более сложную функцию countatom, которая считает элементы-атомы в любом списке.

(defun countatom (lis)

(cond

((null lis) 0)

((atom lis) 1)

(t (apply `+ (mapcar `countatom lis)))

)

)


(countatom `(a (a (b) c) (d) e (f g)))

; 8
^

Функционал FUNCALL

Применяющий функционал FUNCALL аналогичен APPLY, но аргументы он принимает, не в списке, а по отдельности:

(funcall fn x1 x2 ... xN) <=> (fn x1 x2 ... xN)

^

Здесь fn - функция с n aргументами.

(funcall '+ 1 2) ; <=> * (+ 1 2)

; 3


(funcall (car '(+ - / *)) 1 2)

; 3

Пример:

Рассмотрим использование funcall для построения функции map2, которая действует аналогично mapcar, но берет в качестве аргументов два элемента из списка, а не один.

^

Эта функция имеет вид:

(defun map2 (f2 lst)

(cond

((null lst) nil)

(t (cons

(funcall f2 (car lst) (cadr lst))

; выполняем кнкатенацию результаты вызова в-ии f2 для головы и 2го элемента

(map2 f2 (cddr lst)))

; с результатом рекурсивного вызова исходной ф-ии для «укороченного» хвоста

)

)

)


(map2 'list '(A Christie V Nabokov K Vonnegut))

; ((A Christie) (V Nabokov) (K Vonnegut))

^

Встроенные функционалы

Отображающий функционал можно написать самим, а можно и воспользоваться одним из встроенных. Согласно стандарту, в базовую реализацию языка Лисп обычно включены функционалы: map, mapcar, maplist, mapcan, mapcon, mapc, mapl. Каждый из них покомпонентно обработает любой набор списков. Отличаются они схемами выбора аргументов для отображающей функции, характером воздействия на исходные данные и оформлением результатов, передаваемых объемлющим формулам.

Map

( map result-type function sequences ... )

Функция function вызывается на всех первых элементах последовательностей, затем на всех вторых и т.д. Из полученных результатов function формируется результирующая последовательность, строение которой задается параметром result-type с допустимыми значениями cons, list, array, string, NIL.

(map `list `+ `(1 2 3) `(4 5 6))

; = (5 7 9)


Mapcar

( mapcar function list ... )

Функция function применяется к первым элементам списков, затем ко вторым и т.д. Другими словами, function применяется к <головам> методично сокращающихся списков, и результаты применения собираются в результирующий список.

(mapcar `list `(1 2 3) `(4 5 6))

; = ((1 4)(2 5)(3 6))


Maplist

( maplist function list ... )

Функционал аналогичен mapcar, но function применяется к <<хвостам>> списков list, начиная с полного списка.

(maplist `list `(1 2 3) `(4 5 6))

; = (((1 2 3) (4 5 6)) ((2 3) (5 6)) ((3) (6)))


Mapc и Mapl

Оба функционала работают как mapcar и maplist, соответственно, за исключением того, что они в качестве формального результата выдают первый список (своеобразная аналогия с формальными аргументами).

(mapc `list `(1 2 3) `(4 5 6)) ; = (1 2 3)

(mapl `list `(1 2 3) `(4 5 6)) ; = (1 2 3)


Mapcan и Mapcon

И эти два функционала аналогичны mapcar и maplist, но формирование результатов происходит не с помощью операции cons, которая строит данные в новых блоках памяти, а с помощью деструктивной функции nconc, которая при построении новых данных использует память исходных данных, из-за чего исходные данные могут быть искажены.

(mapcan `list `(1 2 3 4)) ; (1 2 3 4)

(mapcon `list `(1 2 3 4)) ; ((1 2 3 4) (2 3 4) (3 4) (4))

Map-into

Функционал отображает результат в конкретную последовательность.

(setq a (list 1 2 3 4) b (list 10 10 10 10)) ; (10 10 10 10)

(map-into a `+ a b) ; (11 12 13 14)
^

Лямбда выражения

Структура МАР функций ограничивает формы отображаемых функций. Так, если мы желаем получить список с элементами x * x + 1 мы должны определить функцию


(defun f1 (x) (+ 1 (* x x)))

(mapcar `f1 `(1 2 3))


Таким образом определяется специальная функция, которая используется только в MAPCAR.

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

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

(mapcar `(lambda (x) (+ 1 (* x x))) `(1 2 3))

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

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

Общая форма записи лямбда-выражений:

(lambda (параметры) <тело функции>)

Пример:

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

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

Можно использовать mapcar:

(defun sqware (xl) (mapcar `sqw xl))

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

(defun sqware (xl)

(cond

(xl (cons (* (car xl) (car xl) )

; квадрат головы списка

; голову вычислять приходится дважды

(sqware (cdr xl))

) ) ) )

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

(defun sqware (xl)

(mapcar `(lambda (x) (* x x)) xl)

)

^

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

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

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

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


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

(defun decart (x y)

(mapcar

`(lambda (i)

(mapcar

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

Дело в том, что функционал mapcar, собирает результаты отображающей функции в общий список с помощью операции 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 (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)

(mapcar `(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 ведет себя как свертка - она сцепляет результаты без сохранения границ между ними. Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.
^

Выводы по применимости функционалов

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

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

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