Введение в функциональное программирование на Python

Рассуждая о функциональном программировании, люди часто начинают выдавать кучу «функциональных» характеристик. Неизменяемые данные, функции первого класса и оптимизация хвостовой рекурсии. Это свойства языка, помогающие писать функциональные программы. Они упоминают мапирование, каррирование и использование функций высшего порядка. Это приёмы программирования, использующиеся для написания функционального кода. Они упоминают распараллеливание, ленивые вычисления и детерменизм. Это преимущества функциональных программ.

Забейте. Функциональный код отличается одним свойством: отсутствием побочных эффектов. Он не полагается на данные вне текущей функции, и не меняет данные, находящиеся вне функции. Все остальные «свойства» можно вывести из этого.

Нефункциональная функция:

a = 0
def increment1():
    global a
    a += 1

Функциональная функция:

def increment2(a):
    return a + 1

Вместо проходов по списку используйте map и reduce

Map

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

Простой map, принимающий список имён и возвращающий список длин:

name_lengths = map(len, ['Маша', 'Петя', 'Вася'])

print name_lengths
# => [4, 4, 3]

Этот map возводит в квадрат каждый элемент:

squares = map(lambda x: x * x, [0, 1, 2, 3, 4])

print squares
# => [0, 1, 4, 9, 16]

Он не принимает именованную функцию, а берёт анонимную, определённую через lambda. Параметры lambda определены слева от двоеточия. Тело функции – справа. Результат возвращается неявным образом.

Нефункциональный код в следующем примере принимает список имён и заменяет их случайными прозвищами.

import random

names = ['Маша', 'Петя', 'Вася']
code_names = ['Шпунтик', 'Винтик', 'Фунтик']

for i in range(len(names)):
    names[i] = random.choice(code_names)

print names
# => ['Шпунтик', 'Винтик', 'Шпунтик']

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

Перепишем это через map:

import random

names = ['Маша', 'Петя', 'Вася']

secret_names = map(lambda x: random.choice(['Шпунтик', 'Винтик', 'Фунтик']), names)

Упражнение 1. Попробуйте переписать следующий код через map. Он принимает список реальных имён и заменяет их прозвищами, используя более надёжный метод.

names = ['Маша', 'Петя', 'Вася']

for i in range(len(names)):
    names[i] = hash(names[i])

print names
# => [6306819796133686941, 8135353348168144921, -1228887169324443034]

Reduce

Reduce принимает функцию и набор пунктов. Возвращает значение, получаемое комбинированием всех пунктов.

Пример простого reduce. Возвращает сумму всех пунктов в наборе:

sum = reduce(lambda a, x: a + x, [0, 1, 2, 3, 4])

print sum
# => 10

x – текущий пункт, а – аккумулятор. Это значение, которое возвращает выполнение lambda на предыдущем пункте. reduce() перебирает все значения, и запускает для каждого lambda на текущих значениях а и х, и возвращает результат в а для следующей итерации.

А чему равно а в первой итерации? Оно равно первому элементу коллекции, и reduce() начинает работать со второго элемента. То есть, первый х будет равен второму предмету набора.

Следующий пример считает, как часто слово «капитан» встречается в списке строк:

sentences = ['капитан джек воробей',
             'капитан дальнего плавания',
             'ваша лодка готова, капитан']

cap_count = 0
for sentence in sentences:
    cap_count += sentence.count('капитан')

print cap_count
# => 3

Тот же код с использованием reduce:

sentences = ['капитан джек воробей',
             'капитан дальнего плавания',
             'ваша лодка готова, капитан']

cap_count = reduce(lambda a, x: a + x.count('капитан'),
                   sentences,
                   0)

А откуда здесь берётся начальное значение а? Оно не может быть вычислено из количества повторений в первой строке. Поэтому оно задаётся как третий аргумент функции reduce().

Почему map и reduce лучше?

Во-первых, они обычно укладываются в одну строку.

Во-вторых, важные части итерации,– коллекция, операция и возвращаемое значение,– всегда находятся в одном месте map и reduce.

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

В-четвёртых, map и reduce – элементарные операции. Вместо построчного чтения циклов читателю проще воспринимать map и reduce, встроенные в сложные алгоритмы.

В-пятых, у них есть много друзей, позволяющих полезное, слегка изменённое поведение этих функций. Например, filter, all, any и find.

Упражнение 2: перепишите следующий код, используя map, reduce и filter. Filter принимает функцию и коллекцию. Возвращает коллекцию тех вещей, для которых функция возвращает True.

people = [{'имя': 'Маша', 'рост': 160},
    {' рост ': 'Саша', ' рост ': 80},
    {'name': 'Паша'}]

height_total = 0
height_count = 0
for person in people:
    if 'рост' in person:
        height_total += person[' рост ']
        height_count += 1

if height_count > 0:
    average_height = height_total / height_count

    print average_height
    # => 120

Пишите декларативно, а не императивно

Следующая программа эмулирует гонку трёх автомобилей. В каждый момент времени машина либо двигается вперёд, либо нет. Каждый раз программа выводит пройденный автомобилями путь. Через пять промежутков времени гонка заканчивается.

Примеры вывода:

 -
 - -
 - -

 - -
 - -
 - - -

 - - -
 - -
 - - -

 - - - -
 - - -
 - - - -

 - - - -
 - - - -
 - - - - -

Текст программы:

from random import random

time = 5
car_positions = [1, 1, 1]

while time:
    # decrease time
    time -= 1

    print ''
    for i in range(len(car_positions)):
        # move car
        if random() > 0.3:
            car_positions[i] += 1

        # draw car
        print '-' * car_positions[i]

Код императивен. Функциональная версия была бы декларативной – она бы описывала, что нужно сделать, а не то, как это надо сделать.

Используем функции

Декларативности можно достичь, вставляя код в функции:

from random import random

def move_cars():
    for i, _ in enumerate(car_positions):
        if random() > 0.3:
            car_positions[i] += 1

def draw_car(car_position):
    print '-' * car_position

def run_step_of_race():
    global time
    time -= 1
    move_cars()

def draw():
    print ''
    for car_position in car_positions:
        draw_car(car_position)

time = 5
car_positions = [1, 1, 1]

while time:
    run_step_of_race()
    draw()

Для понимания программы читатель просматривает основной цикл. «Если осталось время, пройдём один шаг гонки и выведем результат. Снова проверим время». Если читателю надо будет разобраться, как работает шаг гонки, он сможет прочесть его код отдельно.

Комментарии не нужны, код объясняет сам себя.

Разбиение кода на функции делает код более читаемым. Этот приём использует функции, но лишь как подпрограммы. Они упаковывают код, но не делают его функциональным. Функции влияют на окружающий их код и меняют глобальные переменные, а не возвращают значения. Если читатель встречает переменную, ему потребуется найти, откуда она взялась.

Вот функциональная версия этой программы:

from random import random

def move_cars(car_positions):
    return map(lambda x: x + 1 if random() > 0.3 else x,
               car_positions)

def output_car(car_position):
    return '-' * car_position

def run_step_of_race(state):
    return {'time': state['time'] - 1,
            'car_positions': move_cars(state['car_positions'])}

def draw(state):
    print ''
    print '\n'.join(map(output_car, state['car_positions']))

def race(state):
    draw(state)
    if state['time']:
        race(run_step_of_race(state))

race({'time': 5,
      'car_positions': [1, 1, 1]})

Теперь код разбит на функциональные функции. Тому есть три признака. Первый – нет расшаренных переменных. time и car_positions передаются прямиком в race(). Второе – функции принимают параметры. Третье – переменные не меняются внутри функций, все значения возвращаются. Каждый раз, когда run_step_of_race() проделывает следующий шаг, он передаётся опять в следующий.

Вот вам две функции zero() и one():

def zero(s):
    if s[0] == "0":
        return s[1:]

def one(s):
    if s[0] == "1":
        return s[1:]

zero() принимает строку s. Если первый символ – 0, то возвращает остаток строки. Если нет – тогда None. one() делает то же самое, если первый символ – 1.

Представим функцию rule_sequence(). Она принимает строку и список из функций-правил, состоящий из функций zero и one. Она вызывает первое правило, передавая ему строку. Если не возвращено None, то берёт возвращённое значение и вызывает следующее правило. И так далее. Если возвращается None, rule_sequence() останавливается и возвращает None. Иначе – значение последнего правила.

Примеры входных и выходных данных:

print rule_sequence('0101', [zero, one, zero])
# => 1

print rule_sequence('0101', [zero, zero])
# => None

Императивная версия rule_sequence():

def rule_sequence(s, rules):
    for rule in rules:
        s = rule(s)
        if s == None:
            break

    return s

Упражнение 3. Этот код использует цикл. Перепишите его в декларативном виде с использованием рекурсии.

Используйте конвейеры (pipelines)

Теперь перепишем другой вид циклов при помощи приёма под названием конвейер.

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

bands = [{'name': 'sunset rubdown', 'country': 'UK', 'active': False},
         {'name': 'women', 'country': 'Germany', 'active': False},
         {'name': 'a silver mt. zion', 'country': 'Spain', 'active': True}]

def format_bands(bands):
    for band in bands:
        band['country'] = 'Canada'
        band['name'] = band['name'].replace('.', '')
        band['name'] = band['name'].title()

format_bands(bands)

print bands
# => [{'name': 'Sunset Rubdown', 'active': False, 'country': 'Canada'},
#     {'name': 'Women', 'active': False, 'country': 'Canada' },
#     {'name': 'A Silver Mt Zion', 'active': True, 'country': 'Canada'}]

Название функции «format» слишком общее. И вообще, код вызывает некоторое беспокойство. В одном цикле происходят три разные вещи. Значение ключа 'country' меняется на 'Canada'. Убираются точки и первая буква имени меняется на заглавную. Сложно понять, что код должен делать, и сложно сказать, делает ли он это. Его тяжело использовать, тестировать и распараллеливать.

Сравните:

print pipeline_each(bands, [set_canada_as_country,
                            strip_punctuation_from_name,
                            capitalize_names])

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

pipeline_each() перебирает группы по одной, и передаёт их функциям преобразования, вроде set_canada_as_country(). После применения функции ко всем группам, pipeline_each() делает из них список и передаёт следующей.

Посмотрим на функции преобразования.

def assoc(_d, key, value):
    from copy import deepcopy
    d = deepcopy(_d)
    d[key] = value
    return d

def set_canada_as_country(band):
    return assoc(band, 'country', "Canada")

def strip_punctuation_from_name(band):
    return assoc(band, 'name', band['name'].replace('.', ''))

def capitalize_names(band):
    return assoc(band, 'name', band['name'].title())

Каждая связывает ключ группы с новым значением. Без изменения оригинальных данных это тяжело сделать, поэтому мы решаем это с помощью assoc(). Она использует deepcopy() для создания копии переданного словаря. Каждая функция преобразовывает копию и возвращает эту копию.

Всё вроде как нормально. Оригиналы данных защищены от изменений. Но в коде есть два потенциальных места для изменений данных. В strip_punctuation_from_name() создаётся имя без точек через вызов calling replace() с оригинальным именем. В capitalize_names() создаётся имя с первой прописной буквой на основе title() и оригинального имени. Если replace и time не функциональны, то и strip_punctuation_from_name() с capitalize_names() не функциональны.

К счастью, они функциональны. В Python строки неизменяемы. Эти функции работают с копиями строк. Уфф, слава богу.

Такой контраст между строками и словарями (их изменяемостью) в Python демонстрирует преимущества языков типа Clojure. Там программисту не надо думать, не изменит ли он данные. Не изменит.

Упражнение 4. Попробуйте сделать функцию pipeline_each. Задумайтесь над последовательностью операций. Группы – в массиве, передаются по одной для первой функции преобразования. Затем полученный массив передаётся по одной штучке для второй функции, и так далее.



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

set_canada_as_country = call(lambda x: 'Canada', 'country')
strip_punctuation_from_name = call(lambda x: x.replace('.', ''), 'name')
capitalize_names = call(str.title, 'name')

print pipeline_each(bands, [set_canada_as_country,
                            strip_punctuation_from_name,
                            capitalize_names])

Или, жертвуя читаемостью:

print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
                            call(lambda x: x.replace('.', ''), 'name'),
                            call(str.title, 'name')])

Код для call():

def assoc(_d, key, value):
    from copy import deepcopy
    d = deepcopy(_d)
    d[key] = value
    return d

def call(fn, key):
    def apply_fn(record):
        return assoc(record, key, fn(record.get(key)))
    return apply_fn

Что тут у нас происходит.

Один. call – функция высшего порядка, т.к. принимает другую функцию как аргумент и возвращает функцию.

Два. apply_fn() похожа на функции преобразования. Получает запись (группу). Ищет значение record[key]. Вызывает fn. Присваивает результат в копию записи и возвращает её.

Три. call сам ничего не делает. Всю работу делает apply_fn(). В примере использования pipeline_each(), один экземпляр apply_fn() задаёт 'country' значение 'Canada'. Другой – делает первую букву прописной.

Четыре. При выполнении экземпляра apply_fn() функции fn и key не будут доступны в области видимости. Это не аргументы apply_fn() и не локальные переменные. Но доступ к ним будет. При определении функции она сохраняет ссылки на переменные, которые она замыкает – те, что были определены снаружи функции, и используются внутри. При запуске функции переменные ищутся среди локальных, затем среди аргументов, а затем среди ссылок на замкнутые. Там и найдутся fn и key.

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

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

Остаётся ещё одна обработка данных групп. Убрать всё, кроме имени и страны. Функция extract_name_and_country():

def extract_name_and_country(band):
    plucked_band = {}
    plucked_band['name'] = band['name']
    plucked_band['country'] = band['country']
    return plucked_band

print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
                            call(lambda x: x.replace('.', ''), 'name'),
                            call(str.title, 'name'),
                            extract_name_and_country])

# => [{'name': 'Sunset Rubdown', 'country': 'Canada'},
#     {'name': 'Women', 'country': 'Canada'},
#     {'name': 'A Silver Mt Zion', 'country': 'Canada'}]

extract_name_and_country() можно было бы написать в обобщённом виде под названием pluck(). Использовалась бы она так:

print pipeline_each(bands, [call(lambda x: 'Canada', 'country'),
                            call(lambda x: x.replace('.', ''), 'name'),
                            call(str.title, 'name'),
                            pluck(['name', 'country'])])

Упражнение 5. pluck принимает список ключей, которые надо извлечь из записей. Попробуйте её написать. Это буде функция высшего порядка.



И что теперь?

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

Вспомните про Машу, Петю и Васю. Превратите итерации по спискам в map и reduces.

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

Вспомните про группы. Превратите последовательность операций в конвейер.