Содержание

Функции высших порядков

Функции высших порядков

Что такое функции высших порядков

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

FIXME: В питоне функция – это объект. О функции можно думать, как об объекте, который хранит в себе тело функции и знает, какие

операцию

"вызвать функцию". А раз функция – это объект, то её можно сохранить в переменную или передать в качестве аргумента функции.

FIXME: Функция второго порядка – это функция, которая получает на вход функцию первого порядка или возвращает функцию первого порядка. Аналогично определяется функция третьего, четвёртого порядка, и т.п.

FIXME: Обычно не различают функции второго, третьего и т.д. порядков, а говорят о функциях высшего порядка – о функциях, которые оперируют какими-либо функциями.

Простой пример

Предположим, мы хотим описать объект "точка", чтобы потом уметь её рисовать. У этого объекта будет цвет и координаты:

   1 class Point(object):
   2     ...
   3     def __init__(self, ...):
   4         self.x = ...
   5         self.y = ...
   6         self.color = ...

И теперь мы хотим для нашей точки определить кучу методов:

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

У всех этих методов есть одно общее свойство, они все сводятся к простейшим операциями из линейной алгебры и в любом пакете для линейной алгебры в питоне (например, numpy) соответствующие преобразования для векторов есть. Было бы глупо переписывать все эти операции заново.

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

   1 class Point(object):
   2     ...
   3     def apply(self, transformation):
   4         """ ... Here be the docstring ... """
   5         coords = self.x, self.y
   6         new_coords = transformation(coords)
   7         self.x, self.y = new_coords

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

Как этим методом пользоваться? В простейших случаях тоже очень просто:

   1 def shift_right(coords):
   2     x, y = coords
   3     return x + 1, y
   4 
   5 >>> p = Point(1, 2, "red")
   6 >>> p.apply(shift_right)

Главное наблюдение: когда мы функцию упоминаем без скобок после её имени, мы имеем дело с объектом этой функции.

Как получить объект функции

Или, другими словами, что передавать функции высшего порядка.

Не вызывать функцию

Это простейший вариант, который мы как раз рассмотрели в примере.

lambda

Для описания функций в питоне есть две конструкции: def, с которым мы уже давно знакомы, и lambda. lambda – способ несколько сокращённо описывать очень простые функции.

Выражение

   1 a = lambda args: b

в точности эквивалентно выражению:

   1 def a(args):
   2     return b

То есть lambda отличается от def тремя вещами:

lambda может описывать только функции, состоящие из одного выражения, значение которого сразу возвращается
lambda не привязывает функцию к имени, а вместо этого сразу возвращает объект функции – мы можем сразу же передать его в качестве аргумента другой функции
lambda записывается сильно короче

Прошлый пример мы можем переписать так:

   1 >>> p = Point(1, 2, "red")
   2 >>> p.apply(lambda coords: (coords[0]+1, coords[1]))

Замыкания

Идея передавать функции в качестве параметров функциям пришла в питон из функционального программирования. (Наиболее популярные языки функционального программирования – это Lisp, Haskell, Ocaml, Erlang).

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

В питоне есть несколько способов создавать замыкания, и на примерах этих способов я постараюсь разъяснить это понятие.

Замыкание на объекте

FIXME: Если у нас есть объект a и у него есть метод b, которая получает 3 параметра, из них первый self, то в тот момент, когда мы говорим a.b, мы получаем функцию, которая получает 2 параметра, потому, что self уже зафиксирован.

В питоне получить из объекта метод неизменённым труднее, чем сделать замыкание на объекте.

Замыкание на стеке

FIXME: А вот хотим мы сделать универсальные операции вращения или сдвига точки.

   1 def shift(dx, dy):
   2     def transformation(coords):
   3         x, y = coords
   4         new_coords = (x + dx, y + dy)
   5         return new_coords
   6     return transformation
   7 
   8 def rotation(center, phi):
   9     rotmatrix = numpy.matrix([[cos(phi), -sin(phi)],[sin(phi), cos[phi]])
  10     center = numpy.array(center)
  11     def transformation(coords):
  12         shifted = numpy.array(coords)- center
  13         rotated = numpy.dot(rotmatrix, shifted)
  14         unshifted = rotated + center
  15         return unshifted
  16     return transformation

FIXME: обе функции на примере возвращают функции => они функции высшего порядка; функции transformation в обоих случаях используют данные, которых внутри самой функции нет, но они есть во внешней функции;

FIXME: сделано это так: когда мы создаём функцию, в ней мы запоминаем, что для неё является глобальным пространством имён; в данном случае это namespace другой функции;

FIXME: тут картинка на тему

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

   1 a = 1
   2 def f():
   3     return a
   4 a = 2

Т.е. в этом примере вызов f после второго присваивания будет озвращать 2.

Частичное применение

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

Пусть они выглядят примерно так:

   1 def shift(vec1, vec2):
   2     return vec1 + vec2
   3 
   4 def rotate(center, phi, point):
   5     ...
   6     return unshifted

У нас есть примерно два варианта, как поступить в этом случае:

   1 >>> p.apply(lambda coords: shift((1,2), coords))
   2 >>> p.apply(lambda coords: rotate((1,2), 90, coords))

Начиная с питона 2.5 в питоне появился модуль functools, и в нём есть функция partial для частичного применения.

   1 >>> import functools
   2 >>> rotate_transformation = functools.partial(rotate, center=(1,2), phi=90)
   3 >>> p.apply(rotate_tranformation)

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

Встроенные функции высшего порядка

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

map

FIXME: map – применить функцию к каждому элементу списка и вернуть получившийся список; map(f, a) – синоним [f(x) for x in a]

FIXME: в питоне списков может быть больше одного, тогда функция будет применяться к очередному элементу каждого из списков; map(None, a, b, c) отличается от zip(a, b, c) тем, что zip останавливается там, где кто-нибудь кончился, а map останавливается там, где кончились все.

filter

FIXME: filter – вернуть из списка только те элементы, для которых функция вернула истинное значение; filter(f, a) – синоним [x for x in a if f(x)]

List comprehensions и достаточно неказистая модель работы с функциями высшего порядка в питоне делают эти две функции довольно мало полезными. Единственное частое применение у меня: "".join(map(str, items))

reduce

FIXME: Приблизительное определение reduce: reduce(f, [a,b,c,d]) = f(f(f(a,b), c), d); reduce(f, [a,b,c], z) = f(f(f(z, a), b), c) Это весьма головоломная функция, с которой просто работать только в одном случае – когда f – коммутативная операция. Например, reduce(lambda a,b: a+b, list) = sum(list).

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

В питоне 3 эта функция переехала в модуль functools, поэтому в питоне 2.6 и моложе она есть и как самостоятельная функция, и в модуле functools.

operator

Именно для простоты использования в фукциях высшего порядка (и в особенности для всяких приятностей типа частичного применения), в питоне сделали модуль operator, в котором есть легкопроизносимые названия для встроенных операций. Например, в нём есть функция add(a,b), которая является дословным синонимом a+b – и аналогично для всех операций, какие есть в питоне.

Kodomo

Пользователь