Лекция 3.

Что такое функциональное программирование?

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

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

Далее будут подробно рассмотрены описание и использование функций в Python, рекурсия, передача и возврат функций в качестве параметров, обработка последовательностей и итераторы, а также такое понятие как генератор. Будет продемонстрировано, что в Python функции являются объектами (и, значит, могут быть переданы в качестве параметров и возвращены в результате выполнения функций). Кроме того, речь пойдет о том, как можно реализовать некоторые механизмы функционального программирования, не имеющие в Python прямой синтаксической поддержки, но широко распространенные в языках функционального программирования.

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

Как отмечает Дэвид Мертц (David Mertz) в своей статье о функциональном программировании на Python, "функциональное программирование - программирование на функциональных языках (LISP, ML, OCAML, Haskell, ...)", основными атрибутами которых являются:

• "Наличие функций первого класса (функции наравне с другими объектами можно передавать внутрь функций).
• Рекурсия является основной управляющей структурой в программе.
• Обработка списков (последовательностей).
• Запрещение побочных эффектов у функций, что в первую очередь означает отсутствие присваивания (в "чистых" функциональных языках)
• Запрещение операторов, основной упор делается на выражения. Вместо операторов вся программа в идеале - одно выражение с сопутствующими определениями.
• Ключевой вопрос: что нужно вычислить, а не как.
• Использование функций более высоких порядков (функции над функциями над функциями)".

Функциональная программа

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

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

Кстати, бинарные операции "+", "-", "*", "/", которые записываются в выражениях, являются "математическими" функциями над двумя аргументами -- операндами. Их используют настолько часто, что синтаксис языка программирования имеет для них более короткую запись. Модуль operator позволяет представлять эти операции в функциональном стиле:

>>> from operator import add, mul
>>> print add(2, mul(3, 4))
14

Функция: определение и вызов

Как уже говорилось, определить функцию в Python можно двумя способами: с помощью оператора def и lambda-выражения. Первый способ позволяет использовать операторы. При втором - определение функции может быть только выражением.

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

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

Определение функции должно содержать список формальных параметров и тело определения функции. В случае с оператором def функции также задается некоторое имя. Формальные параметры являются локальными именами внутри тела определения функции, а при вызове функции они оказываются связанными с объектами, переданными как фактические параметры. Значения по умолчанию вычисляются в момент выполнения оператора def, и потому в них можно использовать видимые на момент определения имена.

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

Функция одного аргумента:

def swapcase(s):
 return s.swapcase()

print swapcase("ABC")

Функция двух аргументов, один из которых необязателен и имеет значение по умолчанию:

def inc(n, delta=1):
 return n+delta

print inc(12)
print inc(12, 2)

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

def wrap(text, width=70, **kwargs):
 from textwrap import TextWrapper
 # kwargs - словарь с именами и значениями аргументов
 w = TextWrapper(width=width, **kwargs)
 return w.wrap(text)

print wrap("my long text ...", width=4)

Функция произвольного числа аргументов:

def max_min(*args):
 # args - список аргументов в порядке их указания при вызове
 return max(args), min(args)

print max_min(1, 2, -1, 5, 3)

Функция с обычными (позиционными) и именованными аргументами:

def swiss_knife(arg1, *args, **kwargs):
 print arg1
 print args
 print kwargs
 return None

print swiss_knife(1)
print swiss_knife(1, 2, 3, 4, 5)
print swiss_knife(1, 2, 3, a='abc', b='sdf')
# print swiss_knife(1, a='abc', 3, 4) # !!! ошибка

lst = [2, 3, 4, 5]
dct = {'a': 'abc', 'b': 'sdf'}
print swiss_knife(1, *lst, **dct) 

Пример определения функции с помощью lambda-выражения дан ниже:

func = lambda x, y: x + y

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

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

def bin(n):
 """Цифры двоичного представления натурального числа """
 digits = []
 while n > 0:
 n, d = divmod(n, 2)
 digits = [d] + digits
 return digits

print bin(69)

def add(x, y):
 return x + y
addition = add # теперь addition и add - разные имена одного и того же объекта

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

def mylist(val, lst=[]):
 lst.append(val)
 return lst

print mylist(1),
print mylist(2)

Вместо ожидаемого [1] [2] получается [1] [1, 2], так как добавляются элементы к "значению по умолчанию".

Правильный вариант решения будет, например, таким:

def mylist(val, lst=None):
 lst = lst or []
 lst.append(val)
 return lst

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

Рекурсия

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

В следующем примере переписывается функция bin() в рекурсивном варианте:

def bin(n):
 """Цифры двоичного представления натурального числа """
 if n == 0:
 return []
 n, d = divmod(n, 2)
 return bin(n) + [d]

print bin(69)

Здесь видно, что цикл while больше не используется, а вместо него появилось условие окончания рекурсии: условие, при выполнении которого функция не вызывает себя.

Конечно, в погоне за красивым рекурсивным решением не следует упускать из виду эффективность реализации. В частности, пример реализации функции для вычисления n-го числа Фибоначчи это демонстрирует:

def Fib(n):
 if n < 2: 
 return n 
 else:
 return Fib(n-1) + Fib(n-2)

В данном случае количество рекурсивных вызовов растет экспоненциально от числа n, что совсем не соответствует временной сложности решаемой задачи.

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

Функции как параметры и результат

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

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

Функция apply()

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

>>> lst = [1, 2, 3]
>>> dct = {'a': 4, 'b': 5}
>>> apply(max, lst)
3
>>> max(*lst)
3
>>> apply(dict, [], dct)
{'a': 4, 'b': 5}
>>> dict(**dct)
{'a': 4, 'b': 5}

Списковые включения

Для более естественной записи обработки списков в Python 2 была внесена новинка: списковые включения. Фактически это специальный сокращенный синтаксис для вложенных циклов for и условий if, на самом низком уровне которых определенное выражение добавляется к списку, например:

all_pairs = []
for i in range(5):
 for j in range(5):
 if i <= j:
 all_pairs.append((i, j))

Все это можно записать в виде спискового включения так:

all_pairs = [(i, j) for i in range(5) for j in range(5) if i <= j]

Как легко заметить, списковые включения позволяют заменить map() и filter() на более удобные для прочтения конструкции.

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

Функция sum()

Получить сумму элементов можно с помощью функции sum():

>>> sum(range(10))
45

Эта функция работает только для числовых типов, она не может конкатенировать строки. Для конкатенации списка строк следует использовать метод join().

Функция reduce()

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

def sum(lst, start):
 return reduce(lambda x, y: x + y, lst, start)

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

lst = range(10)
f = lambda x, y: (x[0] + y, x[1]+[x[0] + y])
print reduce(f, lst, (0, []))

В итоге получается:

(45, [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])

Функция zip()

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

>>> print zip(range(5), "abcde")
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]