Функциональное программирование HOWTO

Автор:

A. M. Kuchling

Выпуск:

0.32

В этом документе мы рассмотрим возможности языка Python, подходящие для реализации программ в функциональном стиле. После введения в концепцию функционального программирования мы рассмотрим такие возможности языка, как iterators и generators, а также соответствующие библиотечные модули, такие как itertools и functools.

Введение

В этом разделе объясняется базовая концепция функционального программирования; если вам просто интересно узнать о возможностях языка Python, переходите к следующему разделу Итераторы.

Языки программирования поддерживают декомпозицию задач несколькими различными способами:

  • Большинство языков программирования являются процедурными: программы представляют собой списки инструкций, которые указывают компьютеру, что делать с входными данными программы. C, Pascal и даже оболочки Unix - это процедурные языки.

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

  • Объектно-ориентированные программы управляют коллекциями объектов. Объекты имеют внутреннее состояние и поддерживают методы, которые каким-либо образом запрашивают или изменяют это внутреннее состояние. Smalltalk и Java - это объектно-ориентированные языки. C++ и Python - языки, которые поддерживают объектно-ориентированное программирование, но не заставляют использовать объектно-ориентированные возможности.

  • Функциональное программирование разлагает задачу на набор функций. В идеале функции только принимают входные данные и производят выходные, и не имеют никакого внутреннего состояния, которое влияет на выход, получаемый при заданных входных данных. Известные функциональные языки включают семейство ML (Standard ML, OCaml и другие варианты) и Haskell.

Разработчики некоторых компьютерных языков предпочитают делать упор на один конкретный подход к программированию. Это часто затрудняет написание программ, использующих другой подход. Другие языки являются мультипарадигмальными и поддерживают несколько различных подходов. Lisp, C++ и Python - мультипарадигмальные языки; на всех этих языках можно писать программы или библиотеки, которые в значительной степени являются процедурными, объектно-ориентированными или функциональными. В большой программе разные разделы могут быть написаны с использованием разных подходов; например, графический интерфейс может быть объектно-ориентированным, а логика обработки - процедурной или функциональной.

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

Некоторые языки очень строго следят за чистотой и даже не используют операторы присваивания, такие как a=3 или c = a + b, но трудно избежать всех побочных эффектов, таких как печать на экране или запись в файл на диске. Другой пример - вызов функции print() или time.sleep(), ни одна из которых не возвращает полезного значения. Обе они вызываются только для того, чтобы получить побочный эффект - отправить текст на экран или приостановить выполнение на секунду.

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

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

Функциональный дизайн может показаться странным ограничением для работы. Почему вы должны избегать объектов и побочных эффектов? У функционального стиля есть теоретические и практические преимущества:

  • Формальная доказуемость.

  • Модульность.

  • Составляемость.

  • Простота отладки и тестирования.

Формальная доказуемость

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

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

Техника, используемая для доказательства корректности программ, заключается в том, чтобы записать инварианты, свойства входных данных и переменных программы, которые всегда истинны. Затем для каждой строки кода вы показываете, что если инварианты X и Y истинны до выполнения строки, то немного другие инварианты X“ и Y“ истинны после выполнения строки. Так продолжается до тех пор, пока вы не дойдете до конца программы, и тогда инварианты должны соответствовать желаемым условиям на выходе программы.

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

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

Модульность

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

Простота отладки и тестирования

Тестировать и отлаживать программы в функциональном стиле проще.

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

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

Составляемость

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

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

Итераторы

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

Итератор - это объект, представляющий поток данных; этот объект возвращает данные по одному элементу за раз. Итератор Python должен поддерживать метод __next__(), который не принимает аргументов и всегда возвращает следующий элемент потока. Если в потоке больше нет элементов, __next__() должен вызывать исключение StopIteration. Однако итераторы не обязательно должны быть конечными; вполне разумно написать итератор, который выдает бесконечный поток данных.

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

Вы можете экспериментировать с интерфейсом итераций вручную:

>>> L = [1, 2, 3]
>>> it = iter(L)
>>> it  
<...iterator object at ...>
>>> it.__next__()  # same as next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

Python ожидает итерируемые объекты в нескольких различных контекстах, наиболее важным из которых является оператор for. В утверждении for X in Y Y должен быть итератором или некоторым объектом, для которого iter() может создать итератор. Эти два утверждения эквивалентны:

for i in iter(obj):
    print(i)

for i in obj:
    print(i)

Итераторы можно материализовать в виде списков или кортежей с помощью функций-конструкторов list() или tuple():

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)

Распаковка последовательностей также поддерживает итераторы: если вы знаете, что итератор вернет N элементов, вы можете распаковать их в N-кортеж:

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> a, b, c = iterator
>>> a, b, c
(1, 2, 3)

Встроенные функции, такие как max() и min(), могут принимать один аргумент итератора и возвращать наибольший или наименьший элемент. Операторы "in" и "not in" также поддерживают итераторы: X in iterator будет истинным, если X найден в потоке, возвращенном итератором. Вы столкнетесь с очевидными проблемами, если итератор бесконечен; операторы max(), min() никогда не вернутся, а если элемент X никогда не появится в потоке, операторы "in" и "not in" также не вернутся.

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

Типы данных, поддерживающие итераторы

Мы уже видели, как списки и кортежи поддерживают итераторы. Фактически, любой тип последовательности Python, например строки, автоматически поддерживает создание итератора.

Вызов iter() для словаря возвращает итератор, который будет циклически перебирать ключи словаря:

>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
...      'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
>>> for key in m:
...     print(key, m[key])
Jan 1
Feb 2
Mar 3
Apr 4
May 5
Jun 6
Jul 7
Aug 8
Sep 9
Oct 10
Nov 11
Dec 12

Обратите внимание, что начиная с Python 3.7, порядок итераций в словаре гарантированно совпадает с порядком вставки. В более ранних версиях это поведение было неопределенным и могло отличаться в разных реализациях.

Применение iter() к словарю всегда перебирает ключи, но у словарей есть методы, которые возвращают другие итераторы. Если вы хотите выполнить итерацию по значениям или парам ключ/значение, вы можете явно вызвать методы values() или items(), чтобы получить соответствующий итератор.

Конструктор dict() может принимать итератор, возвращающий конечный поток кортежей (key, value):

>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
{'Italy': 'Rome', 'France': 'Paris', 'US': 'Washington DC'}

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

for line in file:
    # do something for each line
    ...

Наборы могут брать свое содержимое из итерируемой таблицы и позволять вам выполнять итерацию по элементам набора:

>>> S = {2, 3, 5, 7, 11, 13}
>>> for i in S:
...     print(i)
2
3
5
7
11
13

Выражения-генераторы и списочные вычисления

Две распространенные операции над выводом итератора: 1) выполнение некоторой операции для каждого элемента; 2) выбор подмножества элементов, удовлетворяющих некоторому условию. Например, если вам нужен список строк, вы можете удалить из каждой строки пробельные символы или извлечь все строки, содержащие заданную подстроку.

Списочные представления и генераторные выражения (сокращенно «listcomps» и «genexps») - это краткая нотация для таких операций, заимствованная из языка функционального программирования Haskell (https://www.haskell.org/). Вы можете удалить все пробельные символы из потока строк с помощью следующего кода:

>>> line_list = ['  line 1\n', 'line 2  \n', ' \n', '']

>>> # Generator expression -- returns iterator
>>> stripped_iter = (line.strip() for line in line_list)

>>> # List comprehension -- returns list
>>> stripped_list = [line.strip() for line in line_list]

Вы можете выбрать только определенные элементы, добавив условие "if":

>>> stripped_list = [line.strip() for line in line_list
...                  if line != ""]

При списочном понимании вы получаете обратно список Python; stripped_list - это список, содержащий результирующие строки, а не итератор. Выражения-генераторы возвращают итератор, который вычисляет значения по мере необходимости, не требуя материализации всех значений сразу. Это означает, что списочные выражения не пригодятся, если вы работаете с итераторами, возвращающими бесконечный поток или очень большой объем данных. В таких ситуациях предпочтительнее использовать выражения-генераторы.

Выражения-генераторы окружены круглыми скобками («()»), а списки-комплименты - квадратными скобками («[]»). Выражения-генераторы имеют вид:

( expression for expr in sequence1
             if condition1
             for expr2 in sequence2
             if condition2
             for expr3 in sequence3
             ...
             if condition3
             for exprN in sequenceN
             if conditionN )

Опять же, для понимания списка отличаются только внешние скобки (квадратные скобки вместо круглых).

Элементами сгенерированного результата будут последовательные значения expression. Все пункты if необязательны; если они присутствуют, то expression оценивается и добавляется к результату только тогда, когда condition истинно.

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

obj_total = sum(obj.count for obj in list_all_objects())

Клаузулы for...in содержат последовательности, по которым будет производиться итерация. Последовательности не обязательно должны быть одинаковой длины, потому что они итерируются слева направо, не параллельно. Для каждого элемента в sequence1 выполняется цикл sequence2 с самого начала. Затем выполняется цикл sequence3 для каждой пары элементов из sequence1 и sequence2.

Другими словами, выражение для понимания списка или генератора эквивалентно следующему коду Python:

for expr1 in sequence1:
    if not (condition1):
        continue   # Skip this element
    for expr2 in sequence2:
        if not (condition2):
            continue   # Skip this element
        ...
        for exprN in sequenceN:
            if not (conditionN):
                continue   # Skip this element

            # Output the value of
            # the expression.

Это означает, что если в списке есть несколько предложений for...in, но нет предложений if, то длина результирующего вывода будет равна произведению длин всех последовательностей. Если у вас есть два списка длины 3, то выходной список будет состоять из 9 элементов:

>>> seq1 = 'abc'
>>> seq2 = (1, 2, 3)
>>> [(x, y) for x in seq1 for y in seq2]  
[('a', 1), ('a', 2), ('a', 3),
 ('b', 1), ('b', 2), ('b', 3),
 ('c', 1), ('c', 2), ('c', 3)]

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

# Syntax error
[x, y for x in seq1 for y in seq2]
# Correct
[(x, y) for x in seq1 for y in seq2]

Генераторы

Генераторы - это особый класс функций, которые упрощают задачу написания итераторов. Обычные функции вычисляют значение и возвращают его, а генераторы возвращают итератор, который возвращает поток значений.

Вы, несомненно, знакомы с тем, как работают обычные вызовы функций в Python или C. Когда вы вызываете функцию, она получает приватное пространство имен, где создаются ее локальные переменные. Когда функция достигает оператора return, локальные переменные уничтожаются, а значение возвращается вызывающему. При последующем вызове той же функции создается новое частное пространство имен и новый набор локальных переменных. Но что, если бы локальные переменные не выбрасывались при выходе из функции? Что если бы вы могли позже возобновить работу функции с того места, на котором она остановилась? Именно это и обеспечивают генераторы; их можно рассматривать как функции с возможностью возобновления.

Вот простейший пример функции-генератора:

>>> def generate_ints(N):
...    for i in range(N):
...        yield i

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

Когда вы вызываете функцию-генератор, она возвращает не одно значение, а объект-генератор, поддерживающий протокол итераторов. При выполнении выражения yield генератор выводит значение i, аналогично оператору return. Существенное различие между выражениями yield и return заключается в том, что при достижении выражения yield состояние выполнения генератора приостанавливается, а локальные переменные сохраняются. При следующем вызове метода __next__() генератора функция возобновит выполнение.

Вот пример использования генератора generate_ints():

>>> gen = generate_ints(3)
>>> gen  
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
Traceback (most recent call last):
  File "stdin", line 1, in <module>
  File "stdin", line 2, in generate_ints
StopIteration

С тем же успехом можно написать for i in generate_ints(5) или a, b, c = generate_ints(3).

Внутри функции-генератора return value вызывает вызов StopIteration(value) из метода __next__(). Как только это произойдет или будет достигнута нижняя часть функции, процессия значений закончится, и генератор не сможет выдавать больше никаких значений.

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

Набор тестов, входящий в состав библиотеки Python, Lib/test/test_generators.py, содержит ряд более интересных примеров. Вот один из них, реализующий последовательный обход дерева с использованием рекурсивных генераторов.

# A recursive generator that generates Tree leaves in in-order.
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x

        yield t.label

        for x in inorder(t.right):
            yield x

Два других примера в test_generators.py дают решения для задачи N-Queens (размещение N ферзей на шахматной доске NxN таким образом, чтобы ни один ферзь не угрожал другому) и задачи Knight’s Tour (поиск маршрута, по которому конь попадает на каждую клетку шахматной доски NxN, не посещая ни одну клетку дважды).

Передача значений в генератор

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

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

val = (yield i)

Я рекомендую всегда ставить круглые скобки вокруг выражения yield, когда вы что-то делаете с возвращаемым значением, как в примере выше. Скобки не всегда необходимы, но проще всегда добавлять их, а не вспоминать, когда они нужны.

(PEP 342 объясняет точные правила, которые заключаются в том, что выражение yield всегда должно быть заключено в круглые скобки, за исключением случаев, когда оно встречается в выражении верхнего уровня в правой части присваивания. Это означает, что вы можете написать val = yield i, но должны использовать круглые скобки, когда есть операция, как в val = (yield i) + 12).

Значения передаются в генератор путем вызова его метода send(value). Этот метод возобновляет работу кода генератора, а выражение yield возвращает указанное значение. Если вызывается регулярный метод __next__(), то выражение yield возвращает значение None.

Вот простой счетчик, который увеличивается на 1 и позволяет изменять значение внутреннего счетчика.

def counter(maximum):
    i = 0
    while i < maximum:
        val = (yield i)
        # If value provided, change counter
        if val is not None:
            i = val
        else:
            i += 1

А вот пример изменения счетчика:

>>> it = counter(10)  
>>> next(it)  
0
>>> next(it)  
1
>>> it.send(8)  
8
>>> next(it)  
9
>>> next(it)  
Traceback (most recent call last):
  File "t.py", line 15, in <module>
    it.next()
StopIteration

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

Помимо send(), есть еще два метода на генераторах:

  • throw(value) используется для того, чтобы вызвать исключение внутри генератора; исключение вызывается выражением yield, в котором выполнение генератора приостанавливается.

  • close() вызывает исключение GeneratorExit внутри генератора, чтобы прервать итерацию. Получив это исключение, код генератора должен либо поднять GeneratorExit, либо StopIteration; перехват исключения и другие действия являются незаконными и вызовут RuntimeError. close() также будет вызван сборщиком мусора Python, когда генератор будет собран.

    Если вам нужно запускать код очистки при возникновении GeneratorExit, я рекомендую использовать набор try: ... finally:, а не ловить GeneratorExit.

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

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

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

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

Две встроенные функции Python, map() и filter(), дублируют возможности генераторов выражений:

map(f, iterA, iterB, ...) возвращает итератор над последовательностью

f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ....

>>> def upper(s):
...     return s.upper()

>>> list(map(upper, ['sentence', 'fragment']))
['SENTENCE', 'FRAGMENT']
>>> [upper(s) for s in ['sentence', 'fragment']]
['SENTENCE', 'FRAGMENT']

Конечно, вы можете добиться того же эффекта с помощью понимания списка.

filter(predicate, iter) возвращает итератор по всем элементам последовательности, удовлетворяющим определенному условию, и аналогичным образом дублируется списочными компиляторами. Предикат** - это функция, возвращающая истинностное значение некоторого условия; для использования с filter() предикат должен принимать единственное значение.

>>> def is_even(x):
...     return (x % 2) == 0

>>> list(filter(is_even, range(10)))
[0, 2, 4, 6, 8]

Это также можно записать в виде списка:

>>> list(x for x in range(10) if is_even(x))
[0, 2, 4, 6, 8]

enumerate(iter, start=0) отсчитывает элементы в итерируемой таблице, возвращая 2-кортежи, содержащие счетчик (от start) и каждый элемент.

>>> for item in enumerate(['subject', 'verb', 'object']):
...     print(item)
(0, 'subject')
(1, 'verb')
(2, 'object')

enumerate() часто используется при циклическом просмотре списка и записи индексов, при которых выполняются определенные условия:

f = open('data.txt', 'r')
for i, line in enumerate(f):
    if line.strip() == '':
        print('Blank line at line #%i' % i)

sorted(iterable, key=None, reverse=False) собирает все элементы итерируемого списка в список, сортирует его и возвращает отсортированный результат. Аргументы key и reverse передаются в метод sort() построенного списка.

>>> import random
>>> # Generate 8 random numbers between [0, 10000)
>>> rand_list = random.sample(range(10000), 8)
>>> rand_list  
[769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
>>> sorted(rand_list)  
[769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
>>> sorted(rand_list, reverse=True)  
[9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]

(Более подробное обсуждение сортировки см. в разделе Техника сортировки).

Встроенные модули any(iter) и all(iter) рассматривают истинностные значения содержимого итерируемого множества. any() возвращает True, если любой элемент итерабельной таблицы является истинным значением, и all() возвращает True, если все элементы являются истинными значениями:

>>> any([0, 1, 0])
True
>>> any([0, 0, 0])
False
>>> any([1, 1, 1])
True
>>> all([0, 1, 0])
False
>>> all([0, 0, 0])
False
>>> all([1, 1, 1])
True

zip(iterA, iterB, ...) берет по одному элементу из каждой итерируемой таблицы и возвращает их в виде кортежа:

zip(['a', 'b', 'c'], (1, 2, 3)) =>
  ('a', 1), ('b', 2), ('c', 3)

Он не строит список в памяти и не перебирает все входные итераторы перед возвратом; вместо этого кортежи строятся и возвращаются, только если они запрошены. (Технический термин для такого поведения - lazy evaluation).

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

zip(['a', 'b'], (1, 2, 3)) =>
  ('a', 1), ('b', 2)

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

Модуль itertools

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

Функции модуля делятся на несколько обширных классов:

  • Функции, создающие новый итератор на основе существующего итератора.

  • Функции для обращения с элементами итератора как с аргументами функции.

  • Функции для выделения частей вывода итератора.

  • Функция для группировки вывода итератора.

Создание новых итераторов

itertools.count(start, step) возвращает бесконечный поток равномерно распределенных значений. В качестве опции можно указать начальное число, которое по умолчанию равно 0, и интервал между числами, который по умолчанию равен 1:

itertools.count() =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
itertools.count(10) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
itertools.count(10, 5) =>
  10, 15, 20, 25, 30, 35, 40, 45, 50, 55, ...

itertools.cycle(iter) сохраняет копию содержимого заданного итератора и возвращает новый итератор, который возвращает его элементы от первого до последнего. Новый итератор будет повторять эти элементы бесконечно.

itertools.cycle([1, 2, 3, 4, 5]) =>
  1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

itertools.repeat(elem, [n]) возвращает указанный элемент n раз, или возвращает элемент бесконечно, если n не указано.

itertools.repeat('abc') =>
  abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ...
itertools.repeat('abc', 5) =>
  abc, abc, abc, abc, abc

itertools.chain(iterA, iterB, ...) принимает на вход произвольное количество итераторов и возвращает все элементы первого итератора, затем все элементы второго, и так далее, пока все итераторы не будут исчерпаны.

itertools.chain(['a', 'b', 'c'], (1, 2, 3)) =>
  a, b, c, 1, 2, 3

itertools.islice(iter, [start], stop, [step]) возвращает поток, являющийся фрагментом итератора. При единственном аргументе stop он вернет первые stop элементов. Если вы укажете начальный индекс, то получите stop-start элементов, а если вы укажете значение step, то элементы будут пропущены соответственно. В отличие от нарезки строк и списков в Python, вы не можете использовать отрицательные значения для start, stop или step.

itertools.islice(range(10), 8) =>
  0, 1, 2, 3, 4, 5, 6, 7
itertools.islice(range(10), 2, 8) =>
  2, 3, 4, 5, 6, 7
itertools.islice(range(10), 2, 8, 2) =>
  2, 4, 6

itertools.tee(iter, [n]) реплицирует итератор; он возвращает n независимых итераторов, которые все возвращают содержимое исходного итератора. Если вы не указали значение n, по умолчанию будет 2. Репликация итераторов требует сохранения части содержимого исходного итератора, поэтому может занимать значительный объем памяти, если итератор большой и один из новых итераторов потребляет больше, чем остальные.

itertools.tee( itertools.count() ) =>
   iterA, iterB

where iterA ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

and   iterB ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Вызов функций на элементах

Модуль operator содержит набор функций, соответствующих операторам Python. Например, operator.add(a, b) (складывает два значения), operator.ne(a, b) (то же, что и a != b) и operator.attrgetter('id') (возвращает вызываемую функцию, которая получает атрибут .id).

itertools.starmap(func, iter) предполагает, что iterable вернет поток кортежей, и вызывает func, используя эти кортежи в качестве аргументов:

itertools.starmap(os.path.join,
                  [('/bin', 'python'), ('/usr', 'bin', 'java'),
                   ('/usr', 'bin', 'perl'), ('/usr', 'bin', 'ruby')])
=>
  /bin/python, /usr/bin/java, /usr/bin/perl, /usr/bin/ruby

Выбор элементов

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

itertools.filterfalse(predicate, iter) является противоположностью filter(), возвращая все элементы, для которых предикат возвращает false:

itertools.filterfalse(is_even, itertools.count()) =>
  1, 3, 5, 7, 9, 11, 13, 15, ...

itertools.takewhile(predicate, iter) возвращает элементы до тех пор, пока предикат возвращает true. Как только предикат возвращает false, итератор сигнализирует о завершении своих результатов.

def less_than_10(x):
    return x < 10

itertools.takewhile(less_than_10, itertools.count()) =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9

itertools.takewhile(is_even, itertools.count()) =>
  0

itertools.dropwhile(predicate, iter) отбрасывает элементы, пока предикат возвращает true, а затем возвращает оставшиеся результаты итерации.

itertools.dropwhile(less_than_10, itertools.count()) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

itertools.dropwhile(is_even, itertools.count()) =>
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

itertools.compress(data, selectors) принимает два итератора и возвращает только те элементы data, для которых соответствующий элемент selectors является истинным, останавливаясь всякий раз, когда один из них исчерпан:

itertools.compress([1, 2, 3, 4, 5], [True, True, False, False, True]) =>
   1, 2, 5

Комбинаторные функции

Функция itertools.combinations(iterable, r) возвращает итератор, содержащий все возможные комбинации r-кортежей из элементов, содержащихся в iterable.

itertools.combinations([1, 2, 3, 4, 5], 2) =>
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 3), (2, 4), (2, 5),
  (3, 4), (3, 5),
  (4, 5)

itertools.combinations([1, 2, 3, 4, 5], 3) =>
  (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5),
  (2, 3, 4), (2, 3, 5), (2, 4, 5),
  (3, 4, 5)

Элементы внутри каждого кортежа располагаются в том же порядке, в каком их вернул iterable. Например, в приведенных выше примерах число 1 всегда стоит перед 2, 3, 4 или 5. Аналогичная функция, itertools.permutations(iterable, r=None), снимает это ограничение на порядок, возвращая все возможные расположения длины r:

itertools.permutations([1, 2, 3, 4, 5], 2) =>
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 1), (2, 3), (2, 4), (2, 5),
  (3, 1), (3, 2), (3, 4), (3, 5),
  (4, 1), (4, 2), (4, 3), (4, 5),
  (5, 1), (5, 2), (5, 3), (5, 4)

itertools.permutations([1, 2, 3, 4, 5]) =>
  (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5),
  ...
  (5, 4, 3, 2, 1)

Если вы не указали значение r, то будет использоваться длина итерируемой таблицы, что означает перестановку всех элементов.

Обратите внимание, что эти функции выдают все возможные комбинации по позиции и не требуют, чтобы содержимое iterable было уникальным:

itertools.permutations('aba', 3) =>
  ('a', 'b', 'a'), ('a', 'a', 'b'), ('b', 'a', 'a'),
  ('b', 'a', 'a'), ('a', 'a', 'b'), ('a', 'b', 'a')

Одинаковый кортеж ('a', 'a', 'b') встречается дважды, но две строки „a“ пришли с разных позиций.

Функция itertools.combinations_with_replacement(iterable, r) снимает другое ограничение: элементы могут повторяться в одном кортеже. Концептуально элемент выбирается для первой позиции каждого кортежа, а затем заменяется перед выбором второго элемента.

itertools.combinations_with_replacement([1, 2, 3, 4, 5], 2) =>
  (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 2), (2, 3), (2, 4), (2, 5),
  (3, 3), (3, 4), (3, 5),
  (4, 4), (4, 5),
  (5, 5)

Группировка элементов

Последняя функция, которую я рассмотрю, itertools.groupby(iter, key_func=None), является самой сложной. key_func(elem) - это функция, которая может вычислить значение ключа для каждого элемента, возвращаемого итерабельной системой. Если вы не зададите функцию ключа, то ключом будет просто сам элемент.

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

city_list = [('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL'),
             ('Anchorage', 'AK'), ('Nome', 'AK'),
             ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ'),
             ...
            ]

def get_state(city_state):
    return city_state[1]

itertools.groupby(city_list, get_state) =>
  ('AL', iterator-1),
  ('AK', iterator-2),
  ('AZ', iterator-3), ...

where
iterator-1 =>
  ('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL')
iterator-2 =>
  ('Anchorage', 'AK'), ('Nome', 'AK')
iterator-3 =>
  ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ')

groupby() предполагает, что содержимое базовой итерируемой таблицы уже отсортировано по ключу. Обратите внимание, что возвращаемые итераторы также используют базовую итерируемую таблицу, поэтому перед запросом итератора-2 и соответствующего ему ключа вы должны использовать результаты итератора-1.

Модуль functools

Модуль functools содержит несколько функций высшего порядка. Функция высшего порядка принимает на вход одну или несколько функций и возвращает новую функцию. Наиболее полезным инструментом в этом модуле является функция functools.partial().

В программах, написанных в функциональном стиле, иногда требуется создавать варианты существующих функций, в которых некоторые параметры заполнены. Рассмотрим функцию Python f(a, b, c); вы можете захотеть создать новую функцию g(b, c), которая эквивалентна f(1, b, c); вы заполняете значение одного из параметров f(). Это называется «частичное применение функции».

Конструктор для partial() принимает аргументы (function, arg1, arg2, ..., kwarg1=value1, kwarg2=value2). Полученный объект является вызываемым, поэтому вы можете просто вызвать его, чтобы вызвать function с заполненными аргументами.

Вот небольшой, но реалистичный пример:

import functools

def log(message, subsystem):
    """Write the contents of 'message' to the specified subsystem."""
    print('%s: %s' % (subsystem, message))
    ...

server_log = functools.partial(log, subsystem='server')
server_log('Unable to open socket')

functools.reduce(func, iter, [initial_value]) суммарно выполняет операцию над всеми элементами итерируемой таблицы и поэтому не может применяться к бесконечным итерируемым таблицам. func должна быть функцией, которая принимает два элемента и возвращает одно значение. functools.reduce() принимает первые два элемента A и B, возвращенные итератором, и вычисляет func(A, B). Затем она запрашивает третий элемент, C, вычисляет func(func(A, B), C), объединяет этот результат с четвертым возвращенным элементом и продолжает до тех пор, пока итератор не исчерпает свой ресурс. Если итератор не возвращает ни одного значения, возникает исключение TypeError. Если задано начальное значение, оно используется в качестве отправной точки и func(initial_value, A) становится первым вычислением.

>>> import operator, functools
>>> functools.reduce(operator.concat, ['A', 'BB', 'C'])
'ABBC'
>>> functools.reduce(operator.concat, [])
Traceback (most recent call last):
  ...
TypeError: reduce() of empty sequence with no initial value
>>> functools.reduce(operator.mul, [1, 2, 3], 1)
6
>>> functools.reduce(operator.mul, [], 1)
1

Если вы используете operator.add() с functools.reduce(), вы сложите все элементы итерируемого множества. Этот случай настолько распространен, что для его вычисления существует специальная встроенная функция sum():

>>> import functools, operator
>>> functools.reduce(operator.add, [1, 2, 3, 4], 0)
10
>>> sum([1, 2, 3, 4])
10
>>> sum([])
0

Однако для многих случаев использования functools.reduce() проще просто написать очевидный цикл for:

import functools
# Instead of:
product = functools.reduce(operator.mul, [1, 2, 3], 1)

# You can write:
product = 1
for i in [1, 2, 3]:
    product *= i

Родственной функцией является itertools.accumulate(iterable, func=operator.add). Она выполняет те же вычисления, но вместо того, чтобы возвращать только конечный результат, accumulate() возвращает итератор, в котором также содержится каждый частичный результат:

itertools.accumulate([1, 2, 3, 4, 5]) =>
  1, 3, 6, 10, 15

itertools.accumulate([1, 2, 3, 4, 5], operator.mul) =>
  1, 2, 6, 24, 120

Модуль оператора

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

Некоторые из функций этого модуля:

  • Математические операции: add(), sub(), mul(), floordiv(), abs(), …

  • Логические операции: not_(), truth().

  • Побитовые операции: and_(), or_(), invert().

  • Сравнения: eq(), ne(), lt(), le(), gt() и ge().

  • Идентификация объекта: is_(), is_not().

Полный список можно найти в документации к модулю оператора.

Малые функции и выражение лямбда

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

Если есть встроенная функция Python или функция модуля, которая подходит для этого, вам не нужно определять новую функцию:

stripped_lines = [line.strip() for line in lines]
existing_files = filter(os.path.exists, file_list)

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

adder = lambda x, y: x+y

print_assign = lambda name, value: name + '=' + str(value)

Альтернативный вариант - просто использовать оператор def и определить функцию обычным способом:

def adder(x, y):
    return x + y

def print_assign(name, value):
    return name + '=' + str(value)

Какая альтернатива предпочтительнее? Это вопрос стиля; я обычно избегаю использования lambda.

Одна из причин моего предпочтения заключается в том, что lambda довольно ограничен в функциях, которые он может определять. Результат должен быть вычисляемым в виде одного выражения, что означает, что вы не можете использовать многосторонние сравнения if... elif... else или операторы try... except. Если вы попытаетесь сделать слишком много в операторе lambda, то в итоге получите слишком сложное выражение, которое трудно читать. Быстро, что делает следующий код?

import functools
total = functools.reduce(lambda a, b: (0, a[1] + b[1]), items)[1]

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

import functools
def combine(a, b):
    return 0, a[1] + b[1]

total = functools.reduce(combine, items)[1]

Но было бы лучше всего, если бы я просто использовал цикл for:

total = 0
for a, b in items:
    total += b

Или встроенный sum() и генераторное выражение:

total = sum(b for a, b in items)

Многие случаи использования functools.reduce() более понятны, если записать их в виде циклов for.

Фредрик Лундх однажды предложил следующий набор правил для рефакторинга использования lambda:

  1. Напишите лямбда-функцию.

  2. Напишите комментарий, объясняющий, что делает эта лямбда.

  3. В течение некоторого времени изучите комментарий и придумайте имя, которое отражает его суть.

  4. Преобразуйте лямбду в оператор def, используя это имя.

  5. Удалите комментарий.

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

История пересмотра и благодарности

Автор хотел бы поблагодарить следующих людей за предложения, исправления и помощь в работе над различными черновиками этой статьи: Ян Бикинг, Ник Коглан, Ник Эффорд, Раймонд Хеттингер, Джим Джуэтт, Майк Крелл, Леандро Ламейро, Юсси Салмела, Коллин Винтер, Блейк Уинтон.

Версия 0.1: опубликована 30 июня 2006 года.

Версия 0.11: опубликована 1 июля 2006 года. Исправлены опечатки.

Версия 0.2: опубликована 10 июля 2006 года. Объединил разделы genexp и listcomp в один. Исправлены опечатки.

Версия 0.21: Добавлены ссылки, предложенные в списке рассылки тьюторов.

Версия 0.30: Добавлена секция о модуле functional, написанная Коллином Винтером; добавлена короткая секция о модуле оператора; несколько других правок.

Ссылки

Общие сведения

Структура и интерпретация компьютерных программ, авторы Гарольд Абельсон и Джеральд Джей Сассман с Джули Сассман. Книгу можно найти на сайте https://mitpress.mit.edu/sicp. В этом классическом учебнике по информатике в главах 2 и 3 рассматривается использование последовательностей и потоков для организации потока данных внутри программы. В книге для примеров используется язык Scheme, но многие подходы к проектированию, описанные в этих главах, применимы и к коду на Python в функциональном стиле.

https://www.defmacro.org/ramblings/fp.html: Общее введение в функциональное программирование, использующее примеры на Java и содержащее пространное историческое введение.

https://en.wikipedia.org/wiki/Functional_programming: Общая статья Википедии, описывающая функциональное программирование.

https://en.wikipedia.org/wiki/Coroutine: Запись для coroutines.

https://en.wikipedia.org/wiki/Partial_application: Ввод понятия частичного применения функции.

https://en.wikipedia.org/wiki/Currying: Запись для понятия «карри».

Специфический для Python

https://gnosis.cx/TPiP/: В первой главе книги Дэвида Мерца Text Processing in Python рассматривается функциональное программирование для обработки текста, в разделе «Использование функций высшего порядка в обработке текста».

Мерц также написал серию из трех статей о функциональном программировании для сайта IBM DeveloperWorks; см. part 1, part 2 и part 3,

Документация по Python

Документация для модуля itertools.

Документация для модуля functools.

Документация для модуля operator.

PEP 289: «Генератор выражений»

PEP 342: «Coroutines via Enhanced Generators» описывает новые возможности генераторов в Python 2.5.