Функции высших порядков:применяющие и отображающие функционалы

Тема: Функционалы языка Лисп.

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

Инструмент для выполнения работы: интерпретатор языка Lisp под Windows – XLispWin.

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- текст программы на языке Лисп, отражающий все пункты индивидуального задания;

- выводы по работе.

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

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

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

Формат функционала APPLY следующий:

(apply fn list),

где fn – функция; list – список аргументов, к которому применяется функция.

Например,

> (apply '* '(2 3))

> .

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

> (setq fun 'car)

CAR

> (apply fun '((a b c d))); обратите внимание на то, что передаваемый аргумент обязательно должен быть списком! Именно поэтому в вызове функционала передаваемый список еще раз обрамлен скобками.

> (setq fun 'cdr)

CDR

> (apply fun '((a b c d)))

(B C D).

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

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

> (apply '(lambda(x y)(* x y)) '(2 34))

68и еще

> (apply '(lambda(lst)(atom (car lst))) '((a s d f)))

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

> ((lambda(lst)(apply '+ lst)) '(2 3 4 5))

> ((lambda(lst)(apply 'cons lst)) '(a (b c)))

(A B C).

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

(funcall fn ar₁ ar₂ … ar_n).

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

> (funcall '+ 2 3)

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

> (funcall fun '(a s d f))

(S D F),

Следующий пример – лямбда-вызов в качестве функционального аргумента:

> (funcall fun '(a s d f))

(S D F)или

> (funcall '(lambda(x lst)(cons x lst)) 'a '(b c d))

(A B C D).

И, наконец, функционал FUNCALL в качестве тела лямбда-вызова:

> ((lambda (fn x)(funcall fn x)) 'cdr '(a b c d))

(B C D)и

> ((lambda (fn x lst)(funcall fn x lst)) 'cons 'a '(b c d))

(A B C D).

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

> (apply 'funcall 'list '(a b c))

(A B C).

Другой важный класс функционалов, которые определенным образом отображают список (последовательность) в новую последовательность или порождают побочный эффект, связанный с исходной последовательностью. Такие функционалы носят название отображающие функционалы или MAP-функционалы. Различают два вида MAP-функционалов, первый из которых применяет функциональный аргумент к CAR-последовательностям списка, а второй – к CDR-последовательностям. Наиболее распространенные из MAP-функционалов – MAPCAR и MAPLIST.

Формат MAPCAR следующий:

(mapcar fn ’(ar₁ ar₂ … ar_n)).

Функционал работает следующим образом: вначале применяется функция к CAR-элементу, затем к CADR-элементу и так далее, до конца списка. Результатом функции будет являться список результатов от применения функционального аргумента ко второму параметру MAPCAR, например,

(mapcar 'atom '(a s d f))

(T T T T).

Прокомментируем этот пример. В данном случае применяется предикат atom в начале к первому элементу списка (a s d f), затем к следующему и так до конца списка. В качестве результата сформирован новый список, состоящий из результатов применения функции к каждому из элементов списка.

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

> (mapcar '+ '(1 2 3 4) '(3 4 5 6))

(4 6 8 10).

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

Использование MAPCAR оправдано во многих случаях, например, его можно применить при создании ассоциативных списков, как, например, в следующем фрагменте:

> (setq a_list (mapcar 'cons '(1 2 3) '(a b c)))

((1. A) (2. B) (3. C))

> a_list

((1. A) (2. B) (3. C))

Теперь со списком a_list можно работать как с полноценным ассоциативным списком.

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

> (mapcar '(lambda(lst1 lst2)(* lst1 lst2)) '(2 3 4) '(3 2 4))

(6 6 16).

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

Для работы хвостовыми частями списков используют функционал MAPLIST, его формат следующий:

(maplist fn list),

где – fn – функциональный аргумент;

– list – список.

MAPLIST работает подобно MAPCAR, но только не над элементами списка, а над CDR-последовательностями списка, причем исходно полагается, что исходный список является собственным хвостом. Например,

> (maplist 'cdr '(a b c))

((B C) (C) NIL).

Работа функционала в данном примере очевидна: применяется функция CDR изначально ко всему списку, затем к хвосту и так далее до конца списка. Результирующий список сформирован из последовательностей применений функционального аргумента к CDR-последовательностям исходного списка.

Оцените и прокомментируйте следующий вызов:

> (maplist 'car '(a b c))

(A B C).

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

> (maplist '(lambda(lst) (reverse lst)) '(a b c d))

((D C B A) (D C B) (D C) (D)) или лямбда-вызов MAPLIST

> ((lambda(fn lst)(maplist fn lst)) 'reverse '(a b c d f))

((F D C B A) (F D C B) (F D C) (F D) (F)).

Следующий пример содержит небольшой «секрет», попробуйте раскрыть его:

> (maplist '(lambda(y)y) '(a b c))

((A B C) (B C) (C)).

Отображающие функционалы чаще всего используются для программирования циклов специального вида. Разновидностью MAPCAR и MAPLIST являются функционалы MAPCAN и MAPCON, которые строят новые списки из результатов, используя структуроразрушающую функцию NCONC.

Примеры использования этих функционалов:

> (mapcon 'reverse '(a s d))

(D S A D S D)

> (mapcan '(lambda(n)((minusp n))(list n)) '(3 -7 4 0 -5 1))

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

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

Рассмотрим отдельные из них.

(some тест список1... списокN) – выполняет действия предиката < тест> над car-обьектами < списка1>, ..., < спискаN>, затем – над cad-обьектами каждого списка и до тех пор, пока тест не вернет значение, отличное от NIL, или не встретится конец списка. Если тест возвращает значение, отличное от NIL, SOME возвращает это значение. Если конец списка достигнут, SOME возвращает NIL.

Примеры:

> (some 'eql '(dog cat cow) '(cow cat dog))

(some 'plusp(list 0 -3 (+4 -6))) NIL.

(notany тест список1... списокN) – выполняет действия предиката < тест> над car-элементами < списка1>, ..., < спискаN>, затем - над cadr-элементами каждого списка и до тех пор, пока тест не выдаст значение, отличное от NIL, или не встретится конец списка. Если тест вернул значение, отличное от NIL, NOTANY возвращает NIL. Если встретился конец списка, NOTANY возвращает Т.

> (notany 'eql '(dog cat cow) '(cow cat dog))

> NIL

> (notany ‘oddp(+3 3) 7/2))

> T.

(every тест список1... списокN) выполняет действия предиката < тест> над car-элементами < списка1>, ..., < спискаN>, затем – над cadr-элементами каждого списка, и т.д. до тех пор, пока тест не выдаст NIL или не встретится конец списка. Если тест выдает NIL, EVERY возвращает NIL. Если встретился конец списка, EVERY возвращает Т.

(every 'eql '(dog cat cow) '(dog cat pig))

> NIL

(every 'oddp (list 3 5 7 11 13))

> T.

(notevery тест список1... списокN) выполняет действия предиката < тест> над car-элементами < списка1>,..., < спискаN>, затем – над cadr-элементами каждого списка, и т.д. до тех пор, пока тест не вернет NIL или не встретится конец списка. Если тест вернет NIL, NOTEVERY возвращает Т. Если встретился конец списка, NOTEVERY возвращает NIL.

(notevery 'eql '(dog cat cow) '(dog cat pig))

> T

(notevery'string< '(bill jack joe) '(bud jim sue))

> NIL.

Индивидуальные задания

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

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

> (apply '* '(20 30))

> (funcall '* 20 30)

600.

2. Выполнить требование пункта 1 текущего задания, используя в качестве функционального аргумента лямбда-вызов, например:

> (funcall '(lambda(h w)(* h w)) 20 30)

600.

Привести аналогичный пример для apply.

3. Выполнить лямбда-вызов выражения, полученного в пункте 1 текущего задания, например,

> ((lambda (h w fn)(funcall fn h w)) 20 30 '*)

600.

Привести аналогичный пример для apply.

4. Привести примеры использования отображающих функционалов mapcar, maplist, по возможности и для mapcan, mapcon (пользуйтесь ими очень осторожно! ), применяя в качестве функционального аргумента известные Вам примитивы языка Лисп (по выбору, но не менее двух), например:

> (mapcar 'cons '(a s d) '(q w e))

((A. Q) (S. W) (D. E)).

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

> (mapcar '(lambda(lst1 lst2)(cons lst1 lst2)) '(a s d) '(q w e))

((A. Q) (S. W) (D. E)).

6. Выполнить лямбда-вызовы отображающих функционалов (не менее двух для каждого вида), например:

> ((lambda (lst1 lst2)

(maplist #'append lst1 lst2)) '(q w e) '(a s d))

((Q W E A S D) (W E S D) (E D)).

7. Привести примеры использования предикатов планирования функций (не менее двух для каждого из приведенных в данной работе).

8. Объяснить результаты, полученные в перечисленных пунктах.

Список рекомендуемой литературы

1.Мир Лиспа. В 2-х т. Т.1: Введение в язык Лисп и функциональное программирование. \Хювёнен Э., Сеппянен Й. Пер. с финск. – М.: Мир, 1990. – 447 с.

2.Мир Лиспа. В 2-х т. Т.2: Методы и системы программирования. \Хювёнен Э., Сеппянен Й. Пер. с финск. – М.: Мир, 1990. – 319 с.

3.Функциональное программирование. Применение и реализация. \Хендерсон П. Пер. с англ. – М.: Мир, 1983. – 349 с.

Оглавление

Лабораторная работа 1………………………………………

Лабораторная работа 2………………………………………

Лабораторная работа 3………………………………………

Лабораторная работа 4………………………………………

Лабораторная работа 5………………………………………

Лабораторная работа 6………………………………………

Лабораторная работа 7………………………………………

Лабораторная работа 8………………………………………

Лабораторная работа 9………………………………………

Лабораторная работа 10……………………………………..

Лабораторная работа 11……………………………………..

⇐ Предыдущая 1 2 3 4 56