## page was renamed from Main/Python/17/Record
<<TableOfContents>>
= Функции высших порядков =

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

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

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

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

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

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

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

{{{#!python
class Point(object):
    ...
    def __init__(self, ...):
        self.x = ...
        self.y = ...
        self.color = ...
}}}

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

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

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

{{{#!python
class Point(object):
    ...
    def apply(self, transformation):
        """ ... Here be the docstring ... """
        coords = self.x, self.y
        new_coords = transformation(coords)
        self.x, self.y = new_coords
}}}

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

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

{{{#!python
def shift_right(coords):
    x, y = coords
    return x + 1, y

>>> p = Point(1, 2, "red")
>>> p.apply(shift_right)
}}}

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

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

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

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

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

=== lambda ===

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

Выражение

{{{#!python
a = lambda args: b
}}}

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

{{{#!python
def a(args):
    return b
}}}

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

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

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

=== Замыкания ===

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

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

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

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

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

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

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

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

{{{#!python
def shift(dx, dy):
    def transformation(coords):
        x, y = coords
        new_coords = (x + dx, y + dy)
        return new_coords
    return transformation

def rotation(center, phi):
    rotmatrix = numpy.matrix([[cos(phi), -sin(phi)],[sin(phi), cos[phi]])
    center = numpy.array(center)
    def transformation(coords):
        shifted = numpy.array(coords)- center
        rotated = numpy.dot(rotmatrix, shifted)
        unshifted = rotated + center
        return unshifted
    return transformation
}}}

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

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

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

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

{{{#!python
a = 1
def f():
    return a
a = 2
}}}

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

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

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

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

{{{#!python
def shift(vec1, vec2):
    return vec1 + vec2

def rotate(center, phi, point):
    ...
    return unshifted
}}}

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

{{{#!python
>>> p.apply(lambda coords: shift((1,2), coords))
>>> p.apply(lambda coords: rotate((1,2), 90, coords))
}}}

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

{{{#!python
>>> import functools
>>> rotate_transformation = functools.partial(rotate, center=(1,2), phi=90)
>>> 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}}} -- и аналогично для всех операций, какие есть
в питоне.

## vim: set et ts=4 sw=4 tw=65: