HOWTO по функциональному программированию

Автор:А. М. Кучлинг
Релиз:0.32

В этом документе мы познакомимся с возможностями Python, подходящими для реализации программ в функциональном стиле. После ознакомления с концепциями функционального программирования мы рассмотрим языковые функции, такие как итератор и генератор и соответствующие библиотечные модули, такие как 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, но трудно избежать всех побочных эффектов. Например, побочными эффектами являются печать на экран или запись в файл на диске. Например, в Python оба вызова функции print() или time.sleep() не возвращают полезного значения; они вызываются только из- за побочных эффектов отправки текста на экран или приостановки выполнения на секунду.

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

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

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

  • Формальная доказуемость.
  • Модульность.
  • Сочетаемость.
  • Лёгкость отладки и тестирования.

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

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

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

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

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

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

Модульность

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

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

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

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

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

Сочетаемость

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

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

Итераторы

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

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

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

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

>>> L = [1, 2, 3]
>>> it = iter(L)
>>> it  #doctest: +ELLIPSIS
<...iterator object at ...>
>>> it.__next__()  # тоже самое что и 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:
    # сделать что-нибудь для каждой строки
    ...

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

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

Генератор выражений и списковые включения

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

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

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

# Выражение генератора - возвращает итератор
stripped_iter = (line.strip() for line in line_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   # Пропустить этот элемент
    for expr2 in sequence2:
        if not (condition2):
            continue   # Пропустить этот элемент
        ...
        for exprN in sequenceN:
            if not (conditionN):
                continue   # Пропустить этот элемент

            # Вывести значение
            # выражения.

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

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

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

# Синтаксическая ошибка
[x, y for x in seq1 for y in seq2]
# Корректно
[(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 байт-кода, который в результате специально компилирует функцию.

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

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

>>> gen = generate_ints(3)
>>> gen  #doctest: +ELLIPSIS
<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, содержит ряд более интересных примеров. Вот один генератор, который реализует обход дерева по порядку с использованием генераторов рекурсивно.

# Рекурсивный генератор, который по порядку генерирует листья дерева.
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-ферзей (размещение N ферзей на шахматной доске NxN, чтобы ни один ферзь не угрожал другому) и Рыцарский тур (поиск маршрута, который ведет коня на каждую клетку поля). Шахматная доска 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 val is not None:
            i = val
        else:
            i += 1

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

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

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

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

  • throw(type, value=None, traceback=None) используется для создания исключения внутри генератора; исключение вызывается выражением 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
>>> # Сгенерировать 8 случайных чисел в диапазоне [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]

(Для более детального объяснения сортировки см. HOWTO по сортировке.)

Встроенные модули 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)

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

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

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) предполагает, что итерируемый объект вернёт поток кортежей, и вызывает 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) возвращает элементы до тех пор, пока предикат возвращает истину. Как только предикат вернет 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) отбрасывает элементы, пока предикат возвращает истину, а затем возвращает остальные результаты итерации.

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() предполагает, что лежащее в основе итерационное содержимое уже будет отсортировано на основе ключа. Обратите внимание, что возвращаемые итераторы также используют базовый итератор, поэтому вы должны использовать результаты iterator-1, прежде чем запрашивать iterator-2 и соответствующий ему ключ.

Модуль functools

Модуль functools в Python 2.5 содержит некоторые функции высшего порядка. Функция высшего порядка принимает одну или несколько функций в качестве входных и возвращает новую функцию. Самый полезный инструмент в этом модуле — функция 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):
    """Записать содержимое 'message' в указанную подсистему."""
    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
# Вместо:
product = functools.reduce(operator.mul, [1, 2, 3], 1)

# Ты можешь написать:
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

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

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

  • Математические операции: add(), sub(), mul(), floordiv(), abs(), …
  • Логические операции: not_(), truth().
  • Побитовые операции: and_(), or_(), invert().
  • Сравнения: eq(), ne(), lt(), le(), gt() и ge().
  • Идентификационный номер объекта: is_(), is_not().

Полный список см. в документации модуля operator.

Небольшие функции и лямбда-выражение

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

Если есть встроенная функция 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 в функциональном стиле.

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

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

Https://en.wikipedia.org/wiki/Coroutine: статья о корутинах.

Https://en.wikipedia.org/wiki/Currying: введение в концепцию каррирования.

Специфичные для Python

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

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

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

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

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

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

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

PEP 342: «Корутины через расширенные генераторы» описывает новые возможности генератора в Python 2.5.