Материалы по курсу «Основы программирования»

Функции как данные, продолжение про итераторы

Функции как данные

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

Пример. Создадим список из нескольких тригонометрических функций:

>>> import math
>>>> trig = [math.sin,
             math.cos,
             math.tan]
>>> trig[1](0)
1.0

В последней строке вывелось 1.0, т.к. в trig[1] находится функция косинуса.

Список параметров в круглых скобках можно приписывать не только к имени, но и к любому выражению. В примере выше мы его приписали к индексации списка: trig[1](0).

Условное выражение

Ранее на лекции мы рассматривали условный оператор вида

if ‹...›:
    ....
elif ‹...›:
    ....
else:
    ....

Но есть в Python и другой синтаксис, который позволяет осуществлять ветвления и внутри выражений:

‹выражение-когда-True› if ‹условие› else ‹выражение-когда-False›

Пример:

>>> x = 10
>>> 100 if x > 5 else 500
100

Здесь условие это x > 5, выражение, когда True — 100, выражение, когда False — 500. Соответственно, сначала вычисляется условие, а потом либо выражение перед if, либо выражение после else.

Условное выражение — выражение, которое, как и любое другое, порождает значение, его можно присвоить переменной:

>>> x = 3
>>> y = 100 if x > 5 else 500
>>> y
500

В этом примере условие x > 5 ложное, поэтому вычисляется вторая ветка 500, результат присваивается переменной y.

Возвращаемся к функциям как данным

Пример. Пусть нам надо вычислить значение sin(x), когда x неотрицательный, cos(x) в противоположном случае.

>>> y = math.sin(x) if x >= 0 else math.cos(x)

Т.к. сама функция является значением, вызов функции можно вынести за скобки:

>>> y = (math.sin if x >= 0 else math.cos)(x)

Выражение в скобках выбирает функцию, затем мы эту функцию вызываем — к скобкам приписан (x) — список аргументов функции.

Функцию, которая была в скобках, можно присвоить переменной:

>>> f = math.sin if x >= 0 else math.cos
>>> y = f(x)

В переменную f кладётся либо синус, либо косинус, в зависимости от знака x. Затем функцию в переменной f вызываем.

Выражения math.sin и math.cos возвращают объекты функций, которые потом будут вызываться.

def — это оператор присваивания! (своеобразный)

Оператор присваивания — это оператор, который кладёт в переменную некоторое значение. Если переменная ранее не была определена, то оператор присваивания её создаёт.

>>> z = 5

Здесь оператор присваивания создал переменную z и присвоил ей (положил в неё) целое число 5.

>>> z = z + 10

Этот оператор присваивания положил в уже существующую переменную целое число 15. Переменная z ранее уже существовала.

А теперь — внимание! def — это оператор создания новой функции, который одновременно является оператором присваивания. Он порождает новую функцию и присваивает её переменной с указанным именем. Т.е.

def ‹имя›(‹параметры›):
    ‹тело функции›

Этот оператор создаст функцию с указанными параметрами и телом и присвоит её переменной с именем ‹имя›. Т.е. ‹имя› — это самая обычная переменная, в которой теперь лежит объект функции.

def square(x):
    return x*x

erauqs = square

Это две равнправные переменные, содержащие одну и ту же функцию. Иначе говоря, одна функция имеет два псевдонима: square и erauqs.

Если мы определили функцию при помощи def, то указанной переменной можно переприсвоить значение, это допустимо в Python:

import math

def square(x):
    return x**2

print(square(0))
square = math.cos
print(square(0))

Эта программа напечатает сначала 0 (квадрат нуля), потом 1.0 (косинус нуля).

Именами переменных являются и встроенные функции, поэтому их можно случайно потерять:

>>> max([1, 3, 2])
3
>>> max = 100500
>>> max([1, 3, 2])
‹ОШИБКА! Нельзя вызвать целое число 100500›

Ещё пример на оператор присваивания def:

if x > 0:
    def f(y):
        return y**2
else:
    def f(y):
        return y**3

Здесь переменной f будет присвоена функция. В случае положительного x — присвоена функция, возвращающая квадрат числа, нуля или отрицательного — возвращающая куб числа.

По смыслу этот пример кода близок к

if x > 0:
    f = 2
else:
    f = 3

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

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

Безымянные функции, lambda

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

Синтаксис:

 lambda ‹параметры›: ‹выражение›

По смыслу эквивалентно функции, создаваемой оператором def, но без присвоения

 def ????(‹параметры›):
     return ‹выражение›

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

Пример. Создадим список из функций, возвращающих степени числа:

>>> powers = [lambda x: 1,
              lambda x: x,
              lambda x: x*x,
              lambda x: x*x*x]
>>> powers[2](7)
49
>>> powers[0](7)
1

Действительно, 7⁰ = 1, 7² = 49.

Пример. Безымянные функции могут быть параметрами безымянных функций:

>>> (lambda f: lambda x: f(f(x)))(lambda a: a*a)(2)
16
>>> (lambda f: lambda x: f(f(x)))(lambda a: a*a)(3)
81

Встроенные функции, принимающие функции

Ряд встроенных функций и методов встроенных типов данных могут принимать функции как параметры. Как правило, в них передают безымянные функции («лямбды»), но можно передавать и любые другие функции.

Функция map(f, xs, ...)

Функция map принимает функцию n аргументов и n итерируемых объектов, возвращает итератор. Рассмотрим сначала простой случай, когда итерируемый объект один:

map(func, xs)

Итератор, возвращаемый map, будет выдавать значения func(xs[0]), func(xs[1]), func(xs[2]) и т.д., пока xs не исчерпается.

Пример. Вычислим квадраты чисел от 0 до 9. Поскольку map возвращает итератор, чтобы увидеть все значения обернём вызов в список:

>>> list(  map(lambda x: x**2, range(10))  )
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

В роли функции испльзовалась безымянная функция lambda x: x**2, возвращающая квадрат числа, исходная последовательность создавалась при помощи range.

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

>>> list(  map(lambda x, y: x*y,  [2, 3, 5, 7, 11], [13, 17, 19, 23])  )
[26, 51, 95, 161]

Аргументом map не обязательно может быть лямбда:

>>> list(  map(len, ['Quick', 'brown', 'fox', 'jumps', 'over', 'dog'])  )
[5, 5, 3, 5, 4, 3]
>>> '+'.join(  map(str, [2, 3, 5, 7, 11, 13])  )
'2+3+5+7+11+13'

Ключи сортировки для list.sort, sorted, max и min

Метод списка .sort и встроенные функции sorted, max и min при сортировке и нахождении наибольшего (или наименьшего) значений сравнивают значения при помощи операций < или >, используют сортировку по умолчанию.

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

Как осуществляется сортировка по умолчанию:

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

Ключ сортировки передаётся в list.sort, sorted, max и min в качестве именованного параметра key. Ключ сортировки является функцией, которая принимает один из элементов последовательности и возвращает значение, которое можно сравнивать при помощи < или >.

Синтасис вызова:

xs.sort(key=‹функция›)
sorted(xs, key=‹функция›)
min(xs, key=‹функция›)
max(xs, key=‹функция›)

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

>>> sorted('the quick brown fox jumps over the lazy dog'.split())
['brown', 'dog', 'fox', 'jumps', 'lazy', 'over', 'quick', 'the', 'the']
>>> sorted('the quick brown fox jumps over the lazy dog'.split(), key=len)
['the', 'fox', 'the', 'dog', 'over', 'lazy', 'quick', 'brown', 'jumps']

Заметим, что в Python сортировка стабильная, т.е. относительный порядок значений с равными ключами сохраняется. В последней отсортированной последовательности вначале расположены трёхбуквенные слова (слова, для которых функция len, назначенная ключом, выдала 3), затем четырёхбуквенные, затем пятибуквенные. При этом и среди трёхбуквенных, и среди четырёхбуквенных, и среди пятибуквенных слов их относительный порядок сохранился. Например, в исходной строке слово fox предшествовало слову dog, в результирующей оно тоже предшествует. Первый артикль the располагался ранее всех других трёхбуквенных слов, второй — между словами fox и dog. В отсортированной последовательности эти отношения сохраняются.

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

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

>>> words = sorted('the quick brown fox jumps over the lazy dog'.split())
>>> words
['brown', 'dog', 'fox', 'jumps', 'lazy', 'over', 'quick', 'the', 'the']
>>> words.sort(key=len)
>>> words
['dog', 'fox', 'the', 'the', 'lazy', 'over', 'brown', 'jumps', 'quick']

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

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

Списки принято использовать для представления набора однородных значений неизвестной длины (длина зависит от входных данных). Кортежи — для совокупности известного набора значений, возможно даже разнородных, длина кортежа при этом фиксирована. Поэтому в качестве ключа принято брать кортеж.

>>> lenalpha = lambda word: (len(word), word)

Здесь мы определили функцию с именем lenalpha, которая вычисляет искомый ключ для слова: формирует пару (кортеж), где нулевой элемент — длина, первый элемент — само слово.

Эту функцию можно было бы определить при помощи def’а:

def lenalpha(word):
    return (len(word), word)

Но поскольку она состоит из одного return’а, её можно создать при помощи lambda и присвоить переменной. К тому же, в консоли удобнее набирать однострочные конструкции.

>>> lenalpha('the')
(3, 'the')
>>> lenalpha('quick')
(5, 'quick')
>>> lenalpha('brown')
(5, 'brown')
>>> lenalpha('fox')
(3, 'fox')

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

>>> (3, 'fox') < (5, 'quick')
True
>>> (5, 'brown') < (3, 'fox')
False
>>> 5 < 3
False
>>> 'brown' < 'fox'
True
>>> (3, 'fox') < (3, 'the')
True
>>> 'fox' < 'the'
True
>>> (5, 'quick') < (5, 'brown')
False
>>> 'quick' < 'brown'
False

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

>>> lenalpha('fox') < lenalpha('quick')
True
>>> lenalpha('brown') < lenalpha('fox')
False

Ну и теперь можем отсортировать исходные слова:

>>> sorted('the quick brown fox jumps over the lazy dog'.split(), key=lenalpha)
['dog', 'fox', 'the', 'the', 'lazy', 'over', 'brown', 'jumps', 'quick']

Можем убедиться, что этот же ключ правильно работает с max и min:

>>> min('the quick brown fox jumps over the lazy dog'.split())
'brown'
>>> min('the quick brown fox jumps over the lazy dog'.split(), key=lenalpha)
'dog'
>>> max('the quick brown fox jumps over the lazy dog'.split())
'the'
>>> max('the quick brown fox jumps over the lazy dog'.split(), key=lenalpha)
'quick'

Функция zip

Вызов функции:

zip(xs, ys, ...)

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

>>> list(   zip('hello', [2, 3, 5, 7, 11, 13])   )
[('h', 2), ('e', 3), ('l', 5), ('l', 7), ('o', 11)]

Мы получили список пар (кортежей из двух элементов).

>>> list(   zip('hello!!!', [2, 3, 5, 7, 11, 13])   )
[('h', 2), ('e', 3), ('l', 5), ('l', 7), ('o', 11), ('!', 13)]

Функции map и zip — ленивые! Что это означает. Это означает, что они вычисляют ровно столько значений, сколько у них попросят.

Пример. Пусть у нас есть функция verbose_square(x), которая вычисляет квадрат числа и сообщает об этом пользователю:

def verbose_square(x):
    res = x * x
    print(x, '*', x, '=', res)
    return res

Если мы её вызовем, она нам сообщит об этом:

>>> z = verbose_square(10)
10 * 10 = 100
>>> z
100

Если мы попробуем получить квадраты чисел при помощи map(), то ничего не произойдёт:

>>> squares = map(verbose_square, [1, 2, 3, 4, 5])
>>> squares
<map iterator>

Функция verbose_square нам ничего не напечатает, потому что ни разу не вызовется — она будет вызываться по мере запроса значений из итератора. Вручную запросить значения можно при помощи встроенной функции next():

>>> next(squares)
1 * 1 = 1
1
>>> a = next(squares)
2 * 2 = 4
>>> a
4

Вызов функции next(squares) для итератора заставляет его вычислить очередное значение. Т.е. первый вызов next(squares) вызовет функцию verbose_square с аргументом 1 (т.е. нулевым элементом списка [1, 2, 3, 4, 5], второй — с аргументом 2 (т.е. первым элементом). Для остальных элементов verbose_square вычисляться не будет, пока мы в третий и последующие разы не вызовем next для итератора прямо или косвенно.

В первом вызове next(squares) первая строчка — то, что нам напечатала verbose_square(), вторая — среда IDLE печатает возвращаемое значение этого вызова.

Во втором вызове мы видим только одну напечатанную строку, потому что оператор присваивания значений не порождает (он только кладёт значение в переменную).

Если мы попробуем построить список из этого итератора, то получим список из трёх чисел — оставшихся значений. При этом для вычисления каждого из них по одному разу вызовется функция verbose_square:

>>> xs = list(squares)
3 * 3 = 9
4 * 4 = 16
5 * 5 = 25
>>> xs
[9, 16, 25]

Итератор дойдёт до конца исходного списка и на последующие запросы будет возвращать исключение (ошибку) StopIteration:

>>> next(squares)
‹сообщение о StopIteration›

Вывод. Значения итератора могут вычисляться ровно на столько, сколько у него «попросят».

Вывод 2. Результат функций map(), zip(), filter() (см. далее) — итератор, а итератор — штука одноразовая. Если мы прочитаем его один раз, то дальнейшее чтение из него нам всегда будет возвращать пустоту (т.е. исключение (ошибку) StopIteration). Поэтому, если результатом функции map() (и других подобных) нужно воспользоваться несколько раз, то его нужно превратить в список — список можем читать сколько угодно — чтение из него каждый раз будет давать новый итератор:

values = list(map(...))
for x in values:
    ...
z = sum(values)
...

Если в примере выше мы не обернём вызов map(...) в list(...), то получим одноразовый итератор, который исчерпается циклом for, и функция sum() увидит пустоту.

Функция filter(f, xs)

Функция принимает функцию f и итерируемый объект xs, возвращает итератор. Элементы, возвращаемые результирующим итератором — это элементы x из xs, для которых функция f(x) вернула истину. Семантику функции filter можно изобразить следующим образом:

def my_filter(f, xs):
    result = []
    for x in xs:
        if f(x):
            result.append(x)

    return iter(result)

На самом деле, семантика my_filter не совсем точно соответствует семантике функции filter, поскольку она сначала целиком читает xs, а потом возвращает итератор для выбранных значений. Встроенная функция filter формирует итератор, который при вызове next() читает из xs значения, пока не найдёт первый подходящий (т.е. для которого функция f вернула истину).

Пример.

def even(n):
    return n % 2 == 0

Консоль:

>>> xs = filter(even, [1, 4, 1, 8, 1, 2])
>>> xs
<filter object at 0x000001A5B83FAD30>
>>> next(xs)
4
>>> next(xs)
8
>>> next(xs)
2
>>> next(xs)
Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    next(xs)
StopIteration
>>> xs = filter(even, [1, 4, 1, 8, 1, 2])
>>> list(xs)
[4, 8, 2]

Если функция имеет вид

def ‹имя›(‹параметры›):
    return ‹выражение›

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

lambda ‹параметры›: ‹выражение›

«Лямбду» можно присвоить переменной (тогда получится эквивалент исходной функции с def:

‹имя› = lambda ‹параметры›: ‹выражение›

А можно и не заводить переменную, а подставить «лямбду» туда, где ранее использовалось имя именованной функции. Например, как аргумент filter():

>>> xs = filter(lambda n: n % 2 == 0, [1, 4, 1, 8, 1, 2])
>>> list(xs)
[4, 8, 2]

Вместо even записана безымянная функция с тем же поведением.

Итог

Функции map() и filter() позволяют компатно записывать некоторые преобразования наборов данных. map() заменяет такой кусок кода:

result = []
for x in xs:
    result.append( ‹выражение c x› )

↓   ↓   ↓

result = map(lambda x: ‹выражение c x›, xs)

filter() заменяет такой кусок кода:

result = []
for x in xs:
    if ‹логическое выражение с x›:
        result.append(x)

↓   ↓   ↓

result = filter(lambda x: ‹логическое выражение с x›, xs)