Редактор Хабрахабра
2,1
рейтинг
14 мая 2015 в 02:25

Разработка → Введение в функциональное программирование на 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]


Моё решение:
names = ['Маша', 'Петя', 'Вася']

secret_names = map(hash, names)



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


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

heights = map(lambda x: x['рост'],
              filter(lambda x: 'рост' in x, people))

if len(heights) > 0:
    from operator import add
    average_height = reduce(add, heights) / len(heights)



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


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

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

 -
 - -
 - -

 - -
 - -
 - - -

 - - -
 - -
 - - -

 - - - -
 - - -
 - - - -

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


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

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. Этот код использует цикл. Перепишите его в декларативном виде с использованием рекурсии.

Моё решение:
def rule_sequence(s, rules):
    if s == None or not rules:
        return s
    else:
        return rule_sequence(rules[0](s), rules[1:])



Используйте конвейеры (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. Задумайтесь над последовательностью операций. Группы – в массиве, передаются по одной для первой функции преобразования. Затем полученный массив передаётся по одной штучке для второй функции, и так далее.

Моё решение:
def pipeline_each(data, fns):
    return reduce(lambda a, x: map(x, a),
                  fns,
                  data)



Все три функции преобразования в результате меняют конкретное поле у группы. 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 принимает список ключей, которые надо извлечь из записей. Попробуйте её написать. Это буде функция высшего порядка.

Моё решение:
def pluck(keys):
    def pluck_fn(record):
        return reduce(lambda a, x: assoc(a, x, record[x]),
                      keys,
                      {})
    return pluck_fn



И что теперь?

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

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

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

Вспомните про группы. Превратите последовательность операций в конвейер.
Перевод: Mary Rose Cook
Вячеслав Голованов @SLY_G
карма
250,2
рейтинг 2,1
Редактор Хабрахабра
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (51)

  • +2
    Это все здорово, но меня тут больше волнует именование переменных. Постоянно в именах не хватает краткости, но сложно бывает не ударяться в крайности. И в итоге половину времени, потраченного на разработку, уходит на выдумывание имени очередной переменной.

    Аргумент _d и переменная d в assoc — это терпимое зло? Пусть даже с учетом краткости функции. Но допустим, что это набор абстрактных данных, пусть. А вот s не слишком ли кратко для последовательности чего-либо кроме символов?

    fn и fns — насколько устоявшиеся сокращения? Всем ли оно понятно с первого взгляда?

    И как таки вы именуете параметры в анонимных функциях? У меня обычно a, b, … или x, y, …. И выбираются как-то интуитивно. А здесь a, x заставили призадуматься даже.
    • +2
      fn/fns — function/functions; сокращения такого вида часто используют в расчетных программах (типа x/xs/xss, y/ys). Также, как i/j/k для счетчика цикла, вполне понятно и предсказуемо.

      a, x — accumulator, x. В том же руби часто используют e в качестве element, a/acc для аккумулятора. Более-менее говорящее имя переменной. Как регистр ax/eax/rax =)
      • 0
        x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.

        Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.
        • 0
          Если вы не заметили, что оно относится только к reduce, то и ваш коллега не заметит. В ruby, вопреки огульному заявлению grossws, используется `memo` для аккумулятора. Достаточно коротко и автореферентно.
          • 0
            Часто встречал acc, как в ruby, так и в scala. В одном проекте стоит использовать консистентное именование, тогда принципиальной разницы между acc и memo не будет.
            • 0
              `acc` это же не совсем `a`, правда? Хотя бы потому, что `[[1,2], [3,4]].each { |a| ...}` ⇐ тут `a` это array.

              Про консистентность согласен.
              • 0
                Процитирую комментарий, на который вы отвечали:
                В том же руби часто используют e в качестве element, a/acc для аккумулятора.
                • 0
                  Процитирую комментарий, на который я отвечал, целиком:

                  x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.
                  Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.

                  Найдете здесь `acc` — с меня пиво :)
                  • 0
                    Ага, вижу. Был уверен, что вы отвечали на мой комментарий, а было только упоминание.
  • +1
    Простите, а почему вдруг map и reduce не принимают именованную функцию, а только lambda?
    def func(arg):
    return arg*arg

    map(func, [2,3])
    >>> [4, 9]

    Мне казалось они могут использовать что угодно вызываемое, хоть метод класса, хоть конструктор
    • +2
      Там речь об аргументе в контексте текущего примера. А примером выше принимается именованная функция.
  • 0
    Что же вы богатую тему генераторов тут не затронули? Вроде примеры подходящие.
    • 0
      Это перевод.
  • +1
    Спасибо за перевод! Для полноты картины я бы добавил ссылку на библиотеку fn.py.
  • +4
    Не описана проблема многоэтажных мапов с лямбдами, где читабельность геометрически регрессирует в связи с тем, что читать приходится с конца, постепенно поднимаясь, без нормальной возможности отладки/временного комментирования/вывода промежуточного результата. Я так и не понял, как можно отлаживать вложенную функциональщину в питоне.

    Набросал пример от балды (извините, что на пасте, тут в карму насрали, теги не работают):
    pastebin.com/1yQnJPDS

    Товарищи ФП-шники, научите меня…
    • +2
      Эта проблема частично нивелируется с помощью пайплайнов, которые описаны в статье. Но в общем случае да, проблема есть, но она решается в функциональных языках различными методами, с помощью комбинаторов, композиций и т.п. Тема отдельная, нужно погружаться глубже, сейчас на это нет времени подробно расписывать, но по ключевым словам можно гуглить дальше.
    • +2
      IMO, в python удобней и читабельней использовать list comprehensions.
      • +1
        Но проблему они не решают, а в многоэтажных обработках только ухудшают читабельность. Там читать приходится с середины, двигаясь глазами в обе стороны: влево — для чтения обработки элемента, вправо — для чтения фильтров.
      • +2
        вот мой пример выше с помощью ФП:
        pastebin.com/1yQnJPDS

        а вот через списковые включения:
        pastebin.com/DD0aG0U7

        читабельность умерла окончательно
  • +2
    people = [{'имя': 'Маша', 'рост': 160},
        {' рост ': 'Саша', ' рост ': 80},
        {'name': 'Паша'}]
    
    heights = map(lambda x: x['рост'],
                  filter(lambda x: 'рост' in x, people))
    
    if len(heights) > 0:
        from operator import add
        average_height = reduce(add, heights) / len(heights)
    


    Я конечно понимаю, что это «упражнение» на map/filter/reduce но зачем писать такую ерунду? Хотя бы

    heights = [x['рост'] for x in people if 'рост' in x]
    if heights:
        average_height = sum(heights) / len(heights)
    
    • 0
      Меня тоже сразу на генераторы неудержимо потянуло, но видимо автор оставил остальной код в классическом виде, чтобы не запутать читателя. А генераторы наверняка разжеваны в другой главе.
      И add, видимо, вытащили, чтобы куда-то впихнуть reduce. Хотя это действительно гланды через задницу… натянутый пример.
  • –2
    Какой-то странный способ обхода списков:
    for i in range(len(names)):
        names[i] = random.choice(code_names)
    

    Не лучше ли:
    for name in names:
        names[names.index(name)] = random.choice(code_names)
    

    ?
    • +3
      Нет, потому что names.index(name) — это линейный поиск элемента.

      можно ещё так:
      for i, _ in enumerate(names):
          names[i] = random.choice(code_names)
      
    • +1
      Возможно, они явно не хотят изменять список во время итерирования по нему. Не могу поверить, что автор статьи не знает о enumerate (хотя вы вот не знаете, похоже :). На мой взгляд, нет ничего страшного в изменении элементов итерируемого списка, размер списка не меняется же.
    • +1
      А потом в списке имен появляются повторяющиеся имена…
      • 0
        Согласен, я понял свою ошибку.
        Но неужели в Питоне хорошо писать вот так, тем более в примере в статье?
        for i in range(len(names)):
        
        • 0
          Тут все зависит от задачи. Что-то делается через map или генераторы списков. Где-то достаточно for i in names. Но если требуется именно цикл по списку/кортежу со знанием ключа текущего элемента, то такая конструкция вполне приемлема. Во-первых, в ней нет ничего плохого. Во-вторых, она смотрится не хуже, чем предложенное выше names.index(name), и не имеет присущих этому варианту недостатков.

          Другой вариант, не менее подходящий, в ответе к тому комментарию имеется.
          • 0
            А почему enumerate рассматриваете не в первых рядах, а в P.S. комментария? Красивее же
            for i_name, name in enumerate(names):
            чем
            for i in range(len(names)):

            Это почти так же как
            for name in names:
            только сразу с индексом и без len().
            • 0
              Потому что перевод?
            • 0
              Потому что пост не об этом. Он о функциональном программировании. Примеры с for i in range(len(names)) здесь используются как примеры того, «как не надо писать» (конечно же, в контексте функционального программирования).

              Нужен был пример «обычного» цикла, и используемый подходил как нельзя лучше.

              Кроме того, в данном примере enumerate как раз и не нужен, так как имя из итератора не берется. Это видно из примера выше: for i, _ in enumerate(names). Вы собираетесь использовать итератор с сущностями, которые вам не нужны. Это просто лишнее усложнение. В вашем же примере вводится еще и новое имя name, которое не нужно.
  • 0
    Вот не хочется переписывать итерации в рекурсивные вызовы, еще и с динамически задаваемой глубиной вызова. Каждый вызов — новый стек и риск переполнения, сами понимаете.

    Можно ли как-то переписать через те же map и reduce?
    Как это решаете в продe? Или не решаете?

    Прим. map и reduce внутри вполне себе императивные и проблемой переполнения вызова страдать не должны:

    bltinmodule.c
    static PyObject *
    builtin_map(PyObject *self, PyObject *args)
    {
        typedef struct {
            PyObject *it;           /* the iterator object */
            int saw_StopIteration;  /* bool:  did the iterator end? */
        } sequence;
    
        PyObject *func, *result;
        sequence *seqs = NULL, *sqp;
        Py_ssize_t n, len;
        register int i, j;
    
        n = PyTuple_Size(args);
        if (n < 2) {
            PyErr_SetString(PyExc_TypeError,
                            "map() requires at least two args");
            return NULL;
        }
    
        func = PyTuple_GetItem(args, 0);
        n--;
    
        if (func == Py_None) {
            if (PyErr_WarnPy3k("map(None, ...) not supported in 3.x; "
                               "use list(...)", 1) < 0)
                return NULL;
            if (n == 1) {
                /* map(None, S) is the same as list(S). */
                return PySequence_List(PyTuple_GetItem(args, 1));
            }
        }
    
        /* Get space for sequence descriptors.  Must NULL out the iterator
         * pointers so that jumping to Fail_2 later doesn't see trash.
         */
        if ((seqs = PyMem_NEW(sequence, n)) == NULL) {
            PyErr_NoMemory();
            return NULL;
        }
        for (i = 0; i < n; ++i) {
            seqs[i].it = (PyObject*)NULL;
            seqs[i].saw_StopIteration = 0;
        }
    
        /* Do a first pass to obtain iterators for the arguments, and set len
         * to the largest of their lengths.
         */
        len = 0;
        for (i = 0, sqp = seqs; i < n; ++i, ++sqp) {
            PyObject *curseq;
            Py_ssize_t curlen;
    
            /* Get iterator. */
            curseq = PyTuple_GetItem(args, i+1);
            sqp->it = PyObject_GetIter(curseq);
            if (sqp->it == NULL) {
                static char errmsg[] =
                    "argument %d to map() must support iteration";
                char errbuf[sizeof(errmsg) + 25];
                PyOS_snprintf(errbuf, sizeof(errbuf), errmsg, i+2);
                PyErr_SetString(PyExc_TypeError, errbuf);
                goto Fail_2;
            }
    
            /* Update len. */
            curlen = _PyObject_LengthHint(curseq, 8);
            if (curlen > len)
                len = curlen;
        }
    
        /* Get space for the result list. */
        if ((result = (PyObject *) PyList_New(len)) == NULL)
            goto Fail_2;
    
        /* Iterate over the sequences until all have stopped. */
        for (i = 0; ; ++i) {
            PyObject *alist, *item=NULL, *value;
            int numactive = 0;
    
            if (func == Py_None && n == 1)
                alist = NULL;
            else if ((alist = PyTuple_New(n)) == NULL)
                goto Fail_1;
    
            for (j = 0, sqp = seqs; j < n; ++j, ++sqp) {
                if (sqp->saw_StopIteration) {
                    Py_INCREF(Py_None);
                    item = Py_None;
                }
                else {
                    item = PyIter_Next(sqp->it);
                    if (item)
                        ++numactive;
                    else {
                        if (PyErr_Occurred()) {
                            Py_XDECREF(alist);
                            goto Fail_1;
                        }
                        Py_INCREF(Py_None);
                        item = Py_None;
                        sqp->saw_StopIteration = 1;
                    }
                }
                if (alist)
                    PyTuple_SET_ITEM(alist, j, item);
                else
                    break;
            }
    
            if (!alist)
                alist = item;
    
            if (numactive == 0) {
                Py_DECREF(alist);
                break;
            }
    
            if (func == Py_None)
                value = alist;
            else {
                value = PyEval_CallObject(func, alist);
                Py_DECREF(alist);
                if (value == NULL)
                    goto Fail_1;
            }
            if (i >= len) {
                int status = PyList_Append(result, value);
                Py_DECREF(value);
                if (status < 0)
                    goto Fail_1;
            }
            else if (PyList_SetItem(result, i, value) < 0)
                goto Fail_1;
        }
    
        if (i < len && PyList_SetSlice(result, i, len, NULL) < 0)
            goto Fail_1;
    
        goto Succeed;
    
    Fail_1:
        Py_DECREF(result);
    Fail_2:
        result = NULL;
    Succeed:
        assert(seqs);
        for (i = 0; i < n; ++i)
            Py_XDECREF(seqs[i].it);
        PyMem_DEL(seqs);
        return result;
    }
    



    _functoolsmodule.c
    /* reduce() *************************************************************/
    
    static PyObject *
    functools_reduce(PyObject *self, PyObject *args)
    {
        PyObject *seq, *func, *result = NULL, *it;
    
        if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))
            return NULL;
        if (result != NULL)
            Py_INCREF(result);
    
        it = PyObject_GetIter(seq);
        if (it == NULL) {
            PyErr_SetString(PyExc_TypeError,
                "reduce() arg 2 must support iteration");
            Py_XDECREF(result);
            return NULL;
        }
    
        if ((args = PyTuple_New(2)) == NULL)
            goto Fail;
    
        for (;;) {
            PyObject *op2;
    
            if (args->ob_refcnt > 1) {
                Py_DECREF(args);
                if ((args = PyTuple_New(2)) == NULL)
                    goto Fail;
            }
    
            op2 = PyIter_Next(it);
            if (op2 == NULL) {
                if (PyErr_Occurred())
                    goto Fail;
                break;
            }
    
            if (result == NULL)
                result = op2;
            else {
                PyTuple_SetItem(args, 0, result);
                PyTuple_SetItem(args, 1, op2);
                if ((result = PyEval_CallObject(func, args)) == NULL)
                    goto Fail;
            }
        }
    
        Py_DECREF(args);
    
        if (result == NULL)
            PyErr_SetString(PyExc_TypeError,
                       "reduce() of empty sequence with no initial value");
    
        Py_DECREF(it);
        return result;
    
    Fail:
        Py_XDECREF(args);
        Py_XDECREF(result);
        Py_DECREF(it);
        return NULL;
    }
    


    • +2
      Рекурсия хорошо работает в тех языках, где компилятор её хорошо оптимизирует (через оптимизацию хвостовой рекурсии). В питоне этой оптимизации нет (по крайней мере в CPython), так что я бы не стал перебарщивать с рекурсией в питоне, но в том же луа или хаскеле — это вполне нормальное решение.
      • +2
        В случае scala есть крайне полезная аннотация @tailrec, которая приведёт в compile-time error, если в аннотированном методе невозможно выполнить tail-call optimization. При компиляции превращается в цикл, естественно.
  • +1
    >> Функциональный код отличается одним свойством: отсутствием побочных эффектов. Он не полагается на данные вне текущей функции, и не меняет данные, находящиеся вне функции. Все остальные «свойства» можно вывести из этого.
    def increment2(a):
        print a
        return a + 1
    


    Вопрос знатокам. Данная функция без побочных эффектов?
    • 0
      Подозреваю, что вопрос риторический, но всё же отвечу =)
      Эта функция с побочными эффектами.
      Но эта функция не проходит критерий «не меняет данные, находящиеся вне функции».
      Потому, что она меняет состояние дескриптора стандартного вывода, который находится вне этой функции.
      Так что всё правильно написал автор.
      • 0
        def draw_car(car_position):
            print '-' * car_position
        

        То есть эта функция имеет побочные эффекты и потому это не функциональное программирование?
        • 0
          Да
          • 0
            А как в исконно-функциональном программировании делать вывод?
            • –1
              В трёх словах: через монаду IO.
              • 0
                А в псевдокоде на питоне можно?)
                • +1
                  Вот эту статью поглядите:
                  www.stephanboyer.com/post/83/monads-for-dummies
                  • 0
                    Не могу понять, как это используется для очищения побочных эффектов.
                    По сути другой интерфейс для того же, не?
                    • +2
                      По сути да, но не совсем. Монада создаёт контекст, в котором вычисляется функция, при этом сама функция может сохранять ссылочную прозрачность. По сути функция, которая возвращает IO String, возвращает не строку, а контекст, из которого можно извлечь строку. А функция, которая принимает IO String, принимает не чистую строку, а опять же контекст со строкой внутри (или, если угодно, обещание строки). Получается, функция как бы не делает никаких побочных эффектов, ничего не читает и ничего не выводит, просто принимает и возвращает чистые немутабельные значения типа «контекст с чем-то внутри», и за счёт этого остаётся чистой. В итоге на выходе из программы, после соединения кучи монад, получаем чистое значение, которое ничего само по себе не читает и не пишет, а только описывает какие-то действия с различными значениями в заданном контексте. А потом уже во время работы программы «грязный» рантайм «выполняет» все эти действия в нужном контексте (например контексте ввода-вывода IO), и мы получаем все побочные эффекты и действия со значениями в них.

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

                      Таким образом мы получаем программу в виде комбинации чистых функций, а вся «грязь» собирается в одном месте, в рантайме.
              • +1
                Монада IO — не какое-то волшебное стредство, которое сделает из функции с побочными эффектами функцию без побочных эффектов.
                • 0
                  Нет, конечно, но это инструмент, который используется для контроля ввода-вывода в ФП, которая позволяет делать ввод-вывод из чистых функций.
        • 0
          Дополню: чтобы такие функции стали чистыми (без побочных эффектов), используют монады.
          • +1
            А также эффекты (Idris) и линейные/уникальные типы (Clean). Монады – лишь один из способов.
            • 0
              Спасибо за информацию, очень интересно было узнать о таких языках. Посмотрел по диагонали инфу об эффектах и уникальных типах. Эффекты по виду те же монады, а уникальные типы похоже выполняют ту же функцию, что и система заимствования в расте, поэтому это не совсем то. Но я могу ошибаться, так что если вы расскажете по эти сущности по подробнее или ткнёте в ссылки на статьи, буду очень благодарен.
              • +1
                Эффекты, наверное, действительно «монады сбоку». А вот суть Clean'а в том, что если система типов гарантирует, что на каждое значение в любой момент времени существует ровно одна ссылка, то можно смело делать IO-функции вида putString : String → *World → *World и getString : *World → (*World, String), и они будут чистыми «от противного» (потому что нельзя функции скормить два раза одно и то же состояние мира и посмотреть, одинаковые ли результаты получатся).
                Кстати, ещё на тему альтернативных подходов к всеобщей чистоте можно глянуть на старый домонадический хаскель с потоковыми IO-функциями вида Request → Response, которые дёргал грязный рантайм.
                • 0
                  То есть полный аналог уникальных ссылок (unique_ptr из С++, &mut T из Rust), причём ближе к &mut T раста.
                • 0
                  А ведь getString : *World -> (*World, String) по виду тоже очень похоже на поднятую в монаду функцию getString вроде getString : IO () -> IO String, контекст описывается через *World. Могу поспорить, что и монадические законы для этой штуки будут работать, хотя доказывать сейчас лень.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.