Забейте. Функциональный код отличается одним свойством: отсутствием побочных эффектов. Он не полагается на данные вне текущей функции, и не меняет данные, находящиеся вне функции. Все остальные «свойства» можно вывести из этого.
Нефункциональная функция:
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.
Вспомните гонки. Разбейте код на функции, и сделайте их функциональными. Превратите цикл в рекурсию.
Вспомните про группы. Превратите последовательность операций в конвейер.
Комментарии (51)
freylis
14.05.2015 06:29+1Простите, а почему вдруг map и reduce не принимают именованную функцию, а только lambda?
def func(arg):
return arg*arg
map(func, [2,3])
>>> [4, 9]
Мне казалось они могут использовать что угодно вызываемое, хоть метод класса, хоть конструктор
gwer
14.05.2015 10:11+2Там речь об аргументе в контексте текущего примера. А примером выше принимается именованная функция.
AlexBin
14.05.2015 12:55+4Не описана проблема многоэтажных мапов с лямбдами, где читабельность геометрически регрессирует в связи с тем, что читать приходится с конца, постепенно поднимаясь, без нормальной возможности отладки/временного комментирования/вывода промежуточного результата. Я так и не понял, как можно отлаживать вложенную функциональщину в питоне.
Набросал пример от балды (извините, что на пасте, тут в карму насрали, теги не работают):
pastebin.com/1yQnJPDS
Товарищи ФП-шники, научите меня…
kstep
14.05.2015 13:02+2Эта проблема частично нивелируется с помощью пайплайнов, которые описаны в статье. Но в общем случае да, проблема есть, но она решается в функциональных языках различными методами, с помощью комбинаторов, композиций и т.п. Тема отдельная, нужно погружаться глубже, сейчас на это нет времени подробно расписывать, но по ключевым словам можно гуглить дальше.
tenzink
14.05.2015 13:11+2IMO, в python удобней и читабельней использовать list comprehensions.
AlexBin
14.05.2015 13:39+1Но проблему они не решают, а в многоэтажных обработках только ухудшают читабельность. Там читать приходится с середины, двигаясь глазами в обе стороны: влево — для чтения обработки элемента, вправо — для чтения фильтров.
AlexBin
14.05.2015 13:58+2вот мой пример выше с помощью ФП:
pastebin.com/1yQnJPDS
а вот через списковые включения:
pastebin.com/DD0aG0U7
читабельность умерла окончательно
hellman
14.05.2015 14:07+2people = [{'имя': 'Маша', 'рост': 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)
sunnyfox
16.05.2015 01:07Меня тоже сразу на генераторы неудержимо потянуло, но видимо автор оставил остальной код в классическом виде, чтобы не запутать читателя. А генераторы наверняка разжеваны в другой главе.
И add, видимо, вытащили, чтобы куда-то впихнуть reduce. Хотя это действительно гланды через задницу… натянутый пример.
serh1o
14.05.2015 14:11-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)
?encyclopedist
14.05.2015 14:20+3Нет, потому что names.index(name) — это линейный поиск элемента.
можно ещё так:
for i, _ in enumerate(names): names[i] = random.choice(code_names)
iroln
14.05.2015 14:32+1Возможно, они явно не хотят изменять список во время итерирования по нему. Не могу поверить, что автор статьи не знает о enumerate (хотя вы вот не знаете, похоже :). На мой взгляд, нет ничего страшного в изменении элементов итерируемого списка, размер списка не меняется же.
gwer
14.05.2015 23:14+1А потом в списке имен появляются повторяющиеся имена…
serh1o
15.05.2015 10:11Согласен, я понял свою ошибку.
Но неужели в Питоне хорошо писать вот так, тем более в примере в статье?
for i in range(len(names)):gwer
15.05.2015 10:41Тут все зависит от задачи. Что-то делается через map или генераторы списков. Где-то достаточно
for i in names. Но если требуется именно цикл по списку/кортежу со знанием ключа текущего элемента, то такая конструкция вполне приемлема. Во-первых, в ней нет ничего плохого. Во-вторых, она смотрится не хуже, чем предложенное вышеnames.index(name), и не имеет присущих этому варианту недостатков.
Другой вариант, не менее подходящий, в ответе к тому комментарию имеется.
JC_Piligrim
15.05.2015 16:23А почему enumerate рассматриваете не в первых рядах, а в P.S. комментария? Красивее же
for i_name, name in enumerate(names):
чем
for i in range(len(names)):
Это почти так же как
for name in names:
только сразу с индексом и без len().gwer
16.05.2015 00:56Потому что пост не об этом. Он о функциональном программировании. Примеры с
for i in range(len(names))здесь используются как примеры того, «как не надо писать» (конечно же, в контексте функционального программирования).
Нужен был пример «обычного» цикла, и используемый подходил как нельзя лучше.
Кроме того, в данном примере enumerate как раз и не нужен, так как имя из итератора не берется. Это видно из примера выше:for i, _ in enumerate(names). Вы собираетесь использовать итератор с сущностями, которые вам не нужны. Это просто лишнее усложнение. В вашем же примере вводится еще и новое имя name, которое не нужно.
Secessus
14.05.2015 16:31Вот не хочется переписывать итерации в рекурсивные вызовы, еще и с динамически задаваемой глубиной вызова. Каждый вызов — новый стек и риск переполнения, сами понимаете.
Можно ли как-то переписать через те же map и reduce?
Как это решаете в продe? Или не решаете?
Прим. map и reduce внутри вполне себе императивные и проблемой переполнения вызова страдать не должны:
bltinmodule.cstatic 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; }kstep
14.05.2015 17:20+2Рекурсия хорошо работает в тех языках, где компилятор её хорошо оптимизирует (через оптимизацию хвостовой рекурсии). В питоне этой оптимизации нет (по крайней мере в CPython), так что я бы не стал перебарщивать с рекурсией в питоне, но в том же луа или хаскеле — это вполне нормальное решение.
grossws
14.05.2015 17:25+2В случае scala есть крайне полезная аннотация
@tailrec, которая приведёт в compile-time error, если в аннотированном методе невозможно выполнить tail-call optimization. При компиляции превращается в цикл, естественно.
HDDimon
14.05.2015 18:08+1>> Функциональный код отличается одним свойством: отсутствием побочных эффектов. Он не полагается на данные вне текущей функции, и не меняет данные, находящиеся вне функции. Все остальные «свойства» можно вывести из этого.
def increment2(a): print a return a + 1
Вопрос знатокам. Данная функция без побочных эффектов?kstep
14.05.2015 18:37Подозреваю, что вопрос риторический, но всё же отвечу =)
Эта функция с побочными эффектами.
Но эта функция не проходит критерий «не меняет данные, находящиеся вне функции».
Потому, что она меняет состояние дескриптора стандартного вывода, который находится вне этой функции.
Так что всё правильно написал автор.
TheShock
15.05.2015 12:19def draw_car(car_position): print '-' * car_position
То есть эта функция имеет побочные эффекты и потому это не функциональное программирование?grossws
15.05.2015 12:22Да
TheShock
15.05.2015 12:32А как в исконно-функциональном программировании делать вывод?
kstep
15.05.2015 12:53-1В трёх словах: через монаду IO.
Lol4t0
15.05.2015 14:08+1Монада IO — не какое-то волшебное стредство, которое сделает из функции с побочными эффектами функцию без побочных эффектов.
kstep
15.05.2015 14:14Нет, конечно, но это инструмент, который используется для контроля ввода-вывода в ФП, которая позволяет делать ввод-вывод из чистых функций.
kstep
15.05.2015 12:32Дополню: чтобы такие функции стали чистыми (без побочных эффектов), используют монады.
Yuuri
20.05.2015 21:30+1А также эффекты (Idris) и линейные/уникальные типы (Clean). Монады – лишь один из способов.
kstep
20.05.2015 22:08Спасибо за информацию, очень интересно было узнать о таких языках. Посмотрел по диагонали инфу об эффектах и уникальных типах. Эффекты по виду те же монады, а уникальные типы похоже выполняют ту же функцию, что и система заимствования в расте, поэтому это не совсем то. Но я могу ошибаться, так что если вы расскажете по эти сущности по подробнее или ткнёте в ссылки на статьи, буду очень благодарен.
Yuuri
22.05.2015 15:54+1Эффекты, наверное, действительно «монады сбоку». А вот суть Clean'а в том, что если система типов гарантирует, что на каждое значение в любой момент времени существует ровно одна ссылка, то можно смело делать IO-функции вида
putString : String > *World > *WorldиgetString : *World > (*World, String), и они будут чистыми «от противного» (потому что нельзя функции скормить два раза одно и то же состояние мира и посмотреть, одинаковые ли результаты получатся).
Кстати, ещё на тему альтернативных подходов к всеобщей чистоте можно глянуть на старый домонадический хаскель с потоковыми IO-функциями видаRequest > Response, которые дёргал грязный рантайм.kstep
22.05.2015 18:09То есть полный аналог уникальных ссылок (unique_ptr из С++, &mut T из Rust), причём ближе к &mut T раста.
kstep
22.05.2015 18:16А ведь
getString : *World -> (*World, String)по виду тоже очень похоже на поднятую в монаду функцию getString вродеgetString : IO () -> IO String, контекст описывается через *World. Могу поспорить, что и монадические законы для этой штуки будут работать, хотя доказывать сейчас лень.
gwer
Это все здорово, но меня тут больше волнует именование переменных. Постоянно в именах не хватает краткости, но сложно бывает не ударяться в крайности. И в итоге половину времени, потраченного на разработку, уходит на выдумывание имени очередной переменной.
Аргумент _d и переменная d в assoc — это терпимое зло? Пусть даже с учетом краткости функции. Но допустим, что это набор абстрактных данных, пусть. А вот s не слишком ли кратко для последовательности чего-либо кроме символов?
fn и fns — насколько устоявшиеся сокращения? Всем ли оно понятно с первого взгляда?
И как таки вы именуете параметры в анонимных функциях? У меня обычно a, b, … или x, y, …. И выбираются как-то интуитивно. А здесь a, x заставили призадуматься даже.
grossws
fn/fns— function/functions; сокращения такого вида часто используют в расчетных программах (типа x/xs/xss, y/ys). Также, какi/j/kдля счетчика цикла, вполне понятно и предсказуемо.a, x— accumulator, x. В том же руби часто используютeв качестве element,a/accдля аккумулятора. Более-менее говорящее имя переменной. Как регистр ax/eax/rax =)gwer
x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.
Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.
matiouchkine
Если вы не заметили, что оно относится только к reduce, то и ваш коллега не заметит. В ruby, вопреки огульному заявлению grossws, используется `memo` для аккумулятора. Достаточно коротко и автореферентно.
grossws
Часто встречал acc, как в ruby, так и в scala. В одном проекте стоит использовать консистентное именование, тогда принципиальной разницы между acc и memo не будет.
matiouchkine
`acc` это же не совсем `a`, правда? Хотя бы потому, что `[[1,2], [3,4]].each { |a| ...}` ? тут `a` это array.
Про консистентность согласен.
grossws
Процитирую комментарий, на который вы отвечали:
matiouchkine
Процитирую комментарий, на который я отвечал, целиком:
x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.
Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.
Найдете здесь `acc` — с меня пиво :)
grossws
Ага, вижу. Был уверен, что вы отвечали на мой комментарий, а было только упоминание.