Kodomo

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

Содержание

  1. Функции высших порядков
    1. Что такое функции высших порядков
    2. Простой пример
    3. Как получить объект функции
      1. Не вызывать функцию
      2. lambda
      3. Замыкания
      4. Замыкание на объекте
      5. Замыкание на стеке
      6. Частичное применение
    4. Встроенные функции высшего порядка
      1. map
      2. filter
      3. reduce
      4. operator

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

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

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 – и аналогично для всех операций, какие есть в питоне.