Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[11]

Лекция восьмая

4.5 Лямбда-исчисление

В первой половине XX века американский математик Алонзо Чёрч предложил использовать для описания частично рекурсивных функций достаточно простой формализм, названный им лямбда-исчислением. Он же сформулировал так называемый тезис Чёрча (на котором базируются тезисы Тьюринга и Маркова) о том, что любая функция, вычислимая в интуитивном смысле эквиватентна некоей частично рекурсивной функции. Этот тезис содержит в себе нестрогое определение, поэтому, с одной стороны, не может быть доказан, а с другой, позволяет упростить некоторые теоретические выкладки. Частично рекурсивные функции суть функции, которые могут зависеть от собственного значения при других входных данных и могут быть определены не для всех входных данных.

Впервые лямбда-выражения появились в языке Лисп в конце 1950-х годов. Позаимствовав термин у Чёрча, его создатели, безусловно, внесли множество изменений. Позже было создано несколько языков чисто функционального типа, как на базе Лиспа (Схема, Лупе, КЛОС, Миранда, Хаскелл), так и сильно отличающихся от него (ФП, МЛ, Хоуп, Эрланг). Функциональное программирование - это отдельная парадигма программирования, где программист задаёт зависимость функций друг от друга, определяя таким образом их свойства и значения. В языках, наиболее точно соответствующих этой концепции, нет переменных, которые могут влиять на контекстную независимость, как мы видели на прошлой лекции. Элементы функционального программирования есть и в питоне.

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

lambda x,y,z:x+y+z

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

R=lambda x,y:pow(x*x+y*y,0.5)

print 11(3,4)

На печать будет выдано 5.0. Сравните ту же самую функцию, объявленную стандартным питоновским способом:

def R(x,y): return рои(х*х+у*у,0.5)

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


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

def genincr(n): return lambda x,i=n:x+i

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

genincr=lambda n:lambda x,i=n:x+i

Это определение функции genincr полностью эквивалентно предыдущему.

Упражнение. Почему нельзя было задать возвращаемую функцию-инкрементатор как lambda х:х+п? (Возможно, если вы затрудняетесь ответить на этот вопрос, вам следует повторить материал прошлой лекции).

4.6 Элементы функционального программирования

Кроме всех этих очевидных применений лямбда-функций, существуют ещё четыре стандартных приёма:

1.Вызов функций - apply().

Выполнять функции можно, как мы знаем, пользуясь скобками: funcO, где func - имя функции. Но в некоторых случаях бывает удобно сначала последовательно подготовить все аргументы, и только потом вызвать функцию. Функция apply принимает два или три аргумента (третий необязателен). Первый - функция: либо имя переменной, содержащей функцию, либо определение лямбда-функции. Второй - кортеж (или другая последовательность, которая внутри функции apply все равно преобразуется в кортеж) с параметрами. Третий аргумент - словарь со всеми именованными параметрами. Так,

А=1,2,[3,4],[5,6] ,7

apply(lambda x,y,z:x[y].append(z),(А,2,В))

аналогично следующему: А=1,2,[3,4],[5,6] ,7 В=2,3

def func(x,y,z):

х[у].append(z) func(A,2,B)

2.Отображение списков - map().


Функция map О порождает новый список из значений функции, примененной к каждому элементу первоначального списка. Легко догадаться, что эта функция берет не менее двух аргументов: функции для применения и последовательности (списка или кортежа) её параметров. В этом случае наша функция должна брать только один параметр. Можно использовать и многопараметрические функции, но в этом случае нужно давать столько списков или кортежей, сколько у неё параметров. Конечно же, они должны быть одинаковой длины. Вне зависимости от типов последовательностей, данных функции тар, она вернет список.

Функция тар является как бы обобщением предыдущей функции, apply, последовательно применяя данную функцию к элементам последовательности. Можно, например, вычислить значения синусов чисел от 1 до 10:

from math import sin map(sin,range(1,10))

Если же нужен не синус, а, скажем, возведение в третью степень, нам поможет лямбда-функция:

map(lambda х:х*х*х,range(1,10))

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

trans=lambda X:map(list,apply(map,[None]+X))

Матрица должна быть представлена в виде списка списков. Это удобное представление не только для работы с элементами, но и для функции apply. Не хватает только первого (точнее, нулевого) элемента - имени функции, что мы и добавляем. Затем выполняется apply, а точнее, тар, собственно транспонирующий наш список списков в список кортежей, что исправляется (нехорошо изменять структуру представления при транспонировании) применением функции list к каждому элементу списка (к каждому кортежу). Запусками нашей функции с различными параметрами можно убедиться, что она работает как для квадратных, так и для прямоугольных матриц.

3. Фильтрация списков - filter().

Функция filter () генерирует новый список из тех элементов исходного списка, для которых проверочная функция истинна. Сами значения элементов при этом не изменяются. Первым аргументом даётся проверочная функция, а вторым следует список (или кортеж, или строка,



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13]