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

Автор:A. M. Kuchling Релиз:0.32

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

Введение

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

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

• Большинство языков программирования - процедурный: программы - это списки инструкций, которые подсказывают компьютеру, что делать с вводом программы. C, Pascal и даже Unix оболочки являются процедурными языками.
• На языках декларативных вы пишете спецификацию, описывающую решаемую проблему, и в языковой реализации определяется, как эффективно выполнять вычисления. SQL - это декларативный язык, с которым вы, скорее всего, знакомы; SQL-запрос описывает набор данных, который требуется извлечь, и модуль SQL решает, нужно ли сканировать таблицы или использовать индексы, какие подклассы должны быть выполнены в первую очередь и т.д.
• Программы Объектно-ориентированный манипулируют коллекциями объектов. Объекты имеют внутренние состояние и поддерживают методы, которые тем или иным образом запрашивают или изменяют эту внутреннюю состояние. Smalltalk и Java являются объектно-ориентированными языками. C и Python являются языками, поддерживающими объектно-ориентированное программирование, но не принудительно использующими объектно-ориентированные функции.
• Программирование функциональная разлагает проблему на набор функций. В идеале функции принимают только входные данные и производят выходные данные, и не имеют внутренних состояние, влияющих на выходной сигнал, производимый для данного входного сигнала. Хорошо известные функциональные языки включают семейство ML (Standard ML, OCaml и другие варианты) и Haskell.

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

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

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

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

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

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

• Формальный provability.
• Модульность.
• Composability.
• Простота отладки и тестирования.

Формальный provability

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

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

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

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

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

Модульность

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

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

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

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

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

Композиционность

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

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

Итераторы

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

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

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

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

>>> L = [1, 2, 3]
>>> it = iter(L)
>>> it  #doctest: +ELLIPSIS
<...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 имеет значение true, если 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) tuples:

>>> 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)

Выражение генератора и представление списка

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

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

line_list = ['  line 1\n', 'line 2  \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 имеет значение true.

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

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]  #doctest: +NORMALIZE_WHITESPACE
[('a', 1), ('a', 2), ('a', 3),
 ('b', 1), ('b', 2), ('b', 3),
 ('c', 1), ('c', 2), ('c', 3)]

Чтобы избежать введения неоднозначности в грамматику Python’s, если 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’а байт-код, который компилирует функцию специально в результат.

При вызове функции генератор она не возвращает ни одного значения; вместо этого возвращается объект генератор, поддерживающий протокол итератора. При выполнении выражения 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’s, 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 queens на шахматной доске NxN, чтобы ни одна королева не угрожала другой) и Knight „s Tour (поиск маршрута, который доставляет рыцаря на каждый квадрат шахматной доски NxN без посещения любого квадрата дважды).

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

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

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

val = (yield i)

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

(PEP 342 поясняет точные правила, которые заключаются в том, что yield-expression всегда должен быть заключен в скобки, за исключением случаев, когда это происходит в выражении верхнего уровня в правой части назначения. Это означает, что вы можете писать 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)  #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’s, когда генератор будет собран из мусора.

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

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

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

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

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

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

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]

(Более подробное описание сортировки см. в документе 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’s строка и нарезки списков нельзя использовать отрицательные значения для 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’s. Некоторые примеры: 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) возвращает элементы до тех пор, пока предикат возвращает значение 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() собирает все последовательные элементы из базового итератора, которые имеют одно и то же значение ключа, и возвращает поток 2-кортежей, содержащих ключевое значение и итератор для элементов с этим ключом.

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() предполагает, что содержимое базового итерабла уже будет отсортировано на основе ключа. Обратите внимание, что возвращенные итераторы также используют базовый итератор, поэтому необходимо использовать результаты итератора-1 перед запросом итератора-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):
    """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’s. Эти функции часто полезны в функциональном стиле код, потому что они избавляют вас от записи тривиальных функций, выполняющих одну операцию.

Некоторые функции в этом модуле:

• Математические операции: 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 обсуждают использование последовательностей и потоков для организации данных с низким уровнем внутри программы. В книге в качестве примеров используется схема, однако многие из описанных в этих главах подходов к кодированию по функциональному стилю применимы к итону код.

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: запись для понятия каррирования.

Определенный для питона

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

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

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

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

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

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

PEP 289: «Выражения генератора»

PEP 342: «Корутины с помощью усиленных генераторов» описывает новые функции генератор в Python 2.5.