5.4 Задание на лабораторную работу

1. Написать функцию, реализующую вычисления, заданные формулой:

Пример:

>(fun 3)

32 ; 1¹ + 2² + 3³

2. Написать функцию, использующую метод Ньютона для вычисления квадратного корня. Метод Ньютона вычисления квадратного корня из числа x начинается с выбора начального приближения y. Это приближение считается достаточно точным, если | x - y² | <= err, где err – некоторая заранее определенная погрешность. В противном случае более точным приближением будет 1/2 *(y + x/y), которое можно вычислить и точно так же подвергнуть проверке на погрешность. Для получения абсолютной величины числа используйте функция abs: (abs -5) = 5.

Пример:

; вычисления квадратного корня из числа 5

; начальное приближение 1

; уровень допустимой погрешности 0.05

>(newton 5 1 0.05)

2.2380953

3. Написать функции для вычисления N-го числа последовательности Фибоначчи. Каждое следующее число последовательности Фибоначчи вычисляется как сумма двух предыдущих. Два первых числа равны единице.

4. Напишите функцию, которая в качестве параметра получает список и возвращает последний элемент этого списка.

Пример:

>(last1 '(a b c))

C

5. Напишите функцию my-nth, которая получает в качестве параметра список l и число n, и возвращает n-ый элемент списка l. Нумерация элементов списка начинается с нуля.

Примеры:

>(my-nth 2 '(0 1 2 3))

2

>(my-nth 0 '((a b) c d))

(A B)

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

• atom - возвращает T, если аргумент является атомом, NIL в противном случае;

• listp - возвращает T, если аргумент является списком.

Примеры:

>(fringe '(a b (c) (d (e) f)))

(A B C D E F)

>(fringe '((((((((a)))))))))

(A)

>(fringe '(((nil) a) 7))

(A 7)

5. 5. Контрольные вопросы

1. Часто, при выполнении каких-либо действий над хвостом списка мы используем предикат null проверки конца списка. Например:

(defun recurse (l)

(if (null l) (do-something)

(do-something-else (car l) (recurse (cdr l)))))

Можно ли вместо предиката null использовать предикат (eql l nil)? Объясните ваш ответ. Объясните также, почему Лисп содержит несколько различных предикатов сравнения.

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

3. Что выполняет следующая рекурсивная функция?

(defun mystery (n)

(cond ((zerop n) 1)

(t (+ n (mystery (- n 1))))))

4. Реализуйте итерационную версию приведенной в предыдущем задании функции mystery.

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

Примеры:

>minimum( '(3 2 7 1 4 8) )

4

6. Ниже приведена функция sum, которая позволяет получить сумму элементов списка, не равных NIL. К сожалению, эта функция работает не совсем правильно: допустим, что входной список содержит только элементы NIL и цифры. Найдите и исправьте ошибки.

(defun sum (lst)

(let ((x (first lst)))

(if (null x)

(sum (rest x))

(+ x (sum (rest x))))))

Лабораторная работа №6 Функционалы, замыкания, макросы

6.1 Цель работы

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

6.2 Теоретические сведения

6.2.1 Функционалы

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

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

Одним из основных типов функционалов являются функционалы, позволяющие применять функциональный аргумент к его параметрам. Такие функционалы называются применяющими или аппликативными функционалами. К применяющим функционалам относятся функции APPLY и FUNCALL.

APPLY является функцией двух аргументов: функции и списка, к элементам которого применяется функция.

Синтаксис функционала APPLY:

(apply fn список)



(fn ’x₁, ’x₂, ..., ’x_n),

где

список=(x₁ x₂ ... x_n)

Например:

>(apply ’+ ’(2 3))

5

>(setq f ’+)

+

>(apply f ’(2 3))

5

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

(funcall fn x1 x2 ... xn)



(fn x1 x2 ... xn)

Например:

>(setq f ’+)

>(funcall f 2 3)

5

Отображающие функционалы

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

(MAP_X fn l₁ l₂ ... l_N)

Здесь l₁ ... l_N – списки, а fn – функция от N аргументов. Как правило, MAP-функция применяется к одному аргументу-списку, т.е. fn является функцией от одного аргумента:

(MAP_X fn список)

MAP-функция применяет функциональный аргумент к каждому элементу списка, заданного вторым аргументом, или к каждому cdr этого списка.

В таблице 6.1 приведены основные типы MAP-функций.

Таблица.6.1. Основные типы Map-функций

	Игнорирование результата	Собирает каждый результат в список	Объединяет результаты в один список
Работает на каждом элементе списка	mapc	mapcar	mapcan
Работает на каждом cdr	mapl	maplist	mapcon

Значение функционала mapcar вычисляется путем применения функции fn к последовательным элементам x_i списка, являющегося вторым аргументом:

(mаpcar fn ’(x₁ x₂ ... x_N))



(list (fn ’x1) (fn ’x2) ... (fn ’x_N))

Например:

>(mapcar ’list ’(1 2 3))

((1) (2) (3))

Функционал maplist работает подобно mapcar, но действия осуществляются не над элементами списка, а над последовательными cdr этого списка. Например:

>(maplist ’list ’(1 2 3))

(((1 2 3)) ((2 3)) ((3)))

Функционалы mapcan и mapcon – аналоги функций mapcar и maplist, но эти функции не строят новый список из результатов, а объединяют результаты в один список:

(mapcan fn ’(x₁ x₂ ... x_N))



(nconc (fn ’x₁) (fn ’x₂) (fn ’x₃) ... (fn ’x_N))

Например:

>(mapcan ’list ’(1 2 3))

(1 2 3)

>(mapcon 'list '(1 2 3))

((1 2 3) (2 3) (3))

Если значением вызова функционального аргумента является NIL, то в объединенном списке его не видно. Это свойство функционалов mapcan и mapcon используется для реализации фильтров: например, можно использовать эти функционалы для удаления элементов, которые удовлетворяют (или не удовлетворяют) определенному условию. Подобную функцию remove-if (удаление элементов, удовлетворяющих условию) можно реализовать следующим образом:

(defun remove-if (funarg list)

(mapcan #’(lambda (elem)

(if (funcall funarg elem) nil

(list elem)))

list))

Теперь для удаления всех цифровых элементов списка (1 a 2 c 3 g) достаточно выполнить следующий вызов функции remove-if:

>remove-if ’numberp ’(1 a 2 c 3 g))

(a c g)

Функционалы mapc и mapl также аналогичны функциям mapcar и maplist, но не собирают и не объединяют результаты. Результаты просто теряются, а в качестве значения возвращается значение второго аргумента функции:

(mapc fn список)



(prog2 (mapcar fn список) список)

Например:

>(mapc ’list ’(1 2 3))

(1 2 3)

>(mapl ’list ’(1 2 3))

(1 2 3)

Функционалы mapc и mapl прежде всего используют для получения побочного эффекта:

>(defun f (u v) (set u v))

F

>(mapc ’f ’(a b c) ’(1 2 3))

(A B C)

>b

2