Функціональне програмування 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 є мультипарадигмальними; ви можете писати програми або бібліотеки, які в основному є процедурними, об’єктно-орієнтованими або функціональними на всіх цих мовах. У великій програмі різні розділи можуть бути написані з використанням різних підходів; GUI може бути об’єктно-орієнтованим, тоді як логіка обробки є процедурною або функціональною, наприклад.

У функціональній програмі введення проходить через набір функцій. Кожна функція працює зі своїм входом і видає певний результат. Функціональний стиль не заохочує функції з побічними ефектами, які змінюють внутрішній стан або вносять інші зміни, які не видно у значенні, що повертається функцією. Функції, які взагалі не мають побічних ефектів, називаються чисто функціональними. Уникати побічних ефектів означає не використовувати структури даних, які оновлюються під час виконання програми; кожен вихід функції повинен залежати лише від її входу.

Деякі мови дуже суворі щодо чистоти й навіть не мають операторів присвоєння, таких як 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. У операторі для X в 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 в ітераторі є істинним, якщо 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() може приймати ітератор, який повертає кінцевий потік кортежів (ключ, значення):

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

Знову ж таки, для розуміння списку відрізняються лише зовнішні дужки (квадратні дужки замість дужок).

Елементи згенерованого результату будуть послідовними значеннями виразу. Речення if є необов’язковими; якщо присутнє, вираз обчислюється та додається до результату лише тоді, коли умова є істинною.

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

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, якщо вираз створює кортеж, він повинен бути оточений дужками. Перше розуміння списку нижче є синтаксичною помилкою, тоді як друге є правильним:

# 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, є функцією-генератором; це виявляється компілятором bytecode Python, який спеціально компілює функцію в результаті.

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

Так само можна написати для i в generate_ints(5) або a, b, c = generate_ints(3).

Усередині функції-генератора повернене значення викликає 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) збирає всі елементи iterable у список, сортує список і повертає відсортований результат. Аргументи 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]

(Для більш детального обговорення сортування див. Sorting HOW TO.)

Вбудовані функції any(iter) і all(iter) переглядають значення істинності вмісту ітерованого елемента. any() повертає True, якщо будь-який елемент в iterable є істинним значенням, а 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, ...) бере по одному елементу з кожного iterable і повертає їх у кортежі:

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

Він не створює список у пам’яті та не вичерпує всі ітератори введення перед поверненням; натомість кортежі створюються та повертаються лише за запитом. (Технічний термін для такої поведінки — лінива оцінка.)

Цей ітератор призначений для використання з ітераторами, які мають однакову довжину. Якщо ітератори мають різну довжину, результуючий потік буде такої ж довжини, як і найкоротший ітератор.

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

Однак вам слід уникати цього, оскільки елемент може бути взято з довших ітераторів і відкинуто. Це означає, що ви не можете продовжувати використовувати ітератори, оскільки ризикуєте пропустити відкинутий елемент.

Модуль itertools

The itertools module contains a number of commonly-used iterators as well as functions for combining several iterators. This section will introduce the module’s contents by showing small examples.

Функції модуля поділяються на кілька широких класів:

  • Функції, які створюють новий ітератор на основі існуючого ітератора.

  • Функції для обробки елементів ітератора як аргументів функції.

  • Функції для вибору частин виводу ітератора.

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

Створення нових ітераторів

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() збирає всі послідовні елементи з основного ітератора, які мають однакове значення ключа, і повертає потік 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

The functools module in Python 2.5 contains some higher-order functions. A higher-order function takes one or more functions as input and returns a new function. The most useful tool in this module is the functools.partial() function.

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

Конструктор для partial() приймає аргументи (функція, arg1, arg2, ..., kwarg1=value1, kwarg2=value2). Отриманий об’єкт можна викликати, тому ви можете просто викликати його, щоб викликати функцію із заповненими аргументами.

Ось маленький, але реалістичний приклад:

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]) кумулятивно виконує операцію над усіма елементами iterable і, отже, не може бути застосовано до нескінченних iterables. 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(), ви додасте всі елементи iterable. Цей випадок настільки поширений, що для його обчислення існує спеціальна вбудована функція під назвою 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

A related function is itertools.accumulate(iterable, func=operator.add). It performs the same calculation, but instead of returning only the final result, accumulate() returns an iterator that also yields each partial result:

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. лямбда приймає кілька параметрів і вираз, що поєднує ці параметри, і створює анонімну функцію, яка повертає значення виразу:

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)

Яка альтернатива є кращою? Це питання стилю; мій звичайний курс — уникати використання лямбда.

Однією з причин моїх переваг є те, що лямбда досить обмежена у функціях, які вона може визначати. Результат має бути обчислюваним як один вираз, що означає, що ви не можете мати багатосторонні порівняння if... elif... else або try... osim операторів. Якщо ви спробуєте зробити занадто багато в операторі лямбда, ви отримаєте надто складний вираз, який важко прочитати. Швидко, що робить наступний код?

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.

Фредрік Лунд одного разу запропонував наступний набір правил для рефакторингу використання лямбда:

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

  2. Напишіть коментар, пояснюючи, що в біса робить ця лямбда.

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

  4. Перетворіть лямбда-вираз на оператор def, використовуючи це ім’я.

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

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

Історія переглядів і подяки

Автор хотів би подякувати наступним особам за пропозиції, виправлення та допомогу з різними чернетками цієї статті: Іен Бікінґ, Нік Коглан, Нік Еффорд, Реймонд Геттінгер, Джим Джеветт, Майк Крелл, Леандро Ламейро, Юссі Салмела, Коллін Вінтер, Блейк Вінтон.

Версія 0.1: опубліковано 30 червня 2006 р.

Версія 0.11: опубліковано 1 липня 2006 р. Виправлення друкарських помилок.

Версія 0.2: опубліковано 10 липня 2006 р. Об’єднано розділи genexp і listcomp в один. Виправлення друкарських помилок.

Версія 0.21: додано більше посилань, запропонованих у списку розсилки викладачів.

Версія 0.30: додано розділ про функціональний модуль, написаний Колліном Вінтером; додає короткий розділ про модуль оператора; кілька інших правок.

Список літератури

Загальний

Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman with Julie Sussman. Full text at https://mitpress.mit.edu/sicp/. In this classic textbook of computer science, chapters 2 and 3 discuss the use of sequences and streams to organize the data flow inside a program. The book uses Scheme for its examples, but many of the design approaches described in these chapters are applicable to functional-style Python code.

http://www.defmacro.org/ramblings/fp.html: A general introduction to functional programming that uses Java examples and has a lengthy historical introduction.

https://en.wikipedia.org/wiki/Functional_programming: загальний запис у Вікіпедії, що описує функціональне програмування.

https://en.wikipedia.org/wiki/Coroutine: Запис для співпрограм.

https://en.wikipedia.org/wiki/Currying: Початок поняття каррі.

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

http://gnosis.cx/TPiP/: The first chapter of David Mertz’s book Text Processing in Python discusses functional programming for text processing, in the section titled «Utilizing Higher-Order Functions in Text Processing».

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

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

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

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

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

PEP 289: «Генератор виразів»

PEP 342: «Сопрограми через розширені генератори» описує нові функції генератора в Python 2.5.