После просмотра курса Programming Languages и прочтения Functional JavaScript захотелось повторить все эти крутые штуки в python. Часть вещей получилось сделать красиво и легко, остальное вышло страшным и непригодным для использования.
Статья включает в себя:
- немного непонятных слов;
- каррирование;
- pattern matching;
- рекурсия (включая хвостовую).
Статья рассчитана на python 3.3+.
Немного непонятных слов
На python можно писать в функциональном стиле, ведь в нем есть анонимные функции:
sum_x_y = lambda x, y: x + y print(sum_x_y(1, 2)) # 3 Функции высшего порядка (принимающие или возвращающие другие функции):
def call_and_twice(fnc, x, y): return fnc(x, y) * 2 print(call_and_twice(sum_x_y, 3, 4)) # 14 Замыкания:
def closure_sum(x): fnc = lambda y: x + y return fnc sum_with_3 = closure_sum(3) print(sum_with_3(12)) # 15 Tuple unpacking(почти pattern matching):
a, b, c = [1, 2, 3] print(a, b, c) # 1 2 3 hd, *tl = range(5) print(hd, 'tl:', *tl) # 0 tl: 1 2 3 4 И крутые модули functools и itertools.
Каррирование
Преобразование функции от многих аргументов в функцию, берущую свои аргументы по одному.
Рассмотрим самый простой случай, каррируем функцию sum_x_y:
sum_x_y_carry = lambda x: lambda y: sum_x_y(x, y) print(sum_x_y_carry(5)(12)) # 17 Что-то совсем не круто, попробуем так:
sum_with_12 = sum_x_y_carry(12) print(sum_with_12(1), sum_with_12(12)) # 13 24 sum_with_5 = sum_x_y_carry(5) print(sum_with_12(10), sum_with_12(17)) # 22 29 Уже интересней, теперь сделаем универсальную функцию для каррирования функций с двумя аргументами, ведь каждый раз писать lambda x: lambda y: zzzz совсем не круто:
curry_2 = lambda fn: lambda x: lambda y: fn(x, y) И применим ее к используемой в реальных проектах функции map:
curry_map_2 = curry_2(map) @curry_map_2 def twice_or_increase(n): if n % 2 == 0: n += 1 if n % 3: n *= 2 return n print(*twice_or_increase(range(10))) # 2 2 3 3 10 10 14 14 9 9 print(*twice_or_increase(range(30))) # 2 2 3 3 10 10 14 14 9 9 22 22 26 26 15 15 34 34 38... Да-да, я использовал каррированый map как декоратор и нивелировал этим отсутствие многострочных лямбд.
Но не все функции принимают 2 аргумента, поэтому сделаем функцию curry_n, используя partial, замыкания и немножко рекурсии:
from functools import partial def curry_n(fn, n): def aux(x, n=None, args=None): # вспомогательная функция args = args + [x] # добавим аргумент в список всех аргументов return partial(aux, n=n - 1, args=args) if n > 1 else fn(*args) # вернем функцию с одним аргументом, созданную из aux либо вызовем изначальную с полученными аргументами return partial(aux, n=n, args=[]) И в очередной раз применим к map, но уже с 3 аргументами:
curry_3_map = curry_n(map, 3) И сделаем функцию для сложения элементов списка с элементами списка 1..10:
sum_arrays = curry_3_map(lambda x, y: x + y) sum_with_range_10 = sum_arrays(range(10)) print(*sum_with_range_10(range(100, 0, -10))) # 100 91 82 73 64 55 46 37 28 19 print(*sum_with_range_10(range(10))) # 0 2 4 6 8 10 12 14 16 18 Так как curry_2 — это частный случай curry_n, то можно сделать:
curry_2 = partial(curry_n, n=2) И для примера применим его к filter:
curry_filter = curry_2(filter) only_odd = curry_filter(lambda n: n % 2) print(*only_odd(range(10))) # 1 3 5 7 9 print(*only_odd(range(-10, 0, 1))) # -9 -7 -5 -3 -1
Pattern matching
Метод анализа списков или других структур данных на наличие в них заданных образцов.
Pattern matching — это то, что больше всего мне понравилось в sml и хуже всего вышло в python.
Придумаем себе цель — написать функцию, которая:
- если принимает список чисел, возвращает их произведение;
- если принимает список строк, возвращает одну большую объединенную строку.
Создадим вспомогательный exception и функцию для его «бросания», которую будем использовать, когда сопоставление не проходит:
class NotMatch(Exception): """Not match""" def not_match(x): raise NotMatch(x) И функцию, которая делает проверку и возвращает объект, либо бросает exception:
match = lambda check, obj: obj if check(obj) else not_match(obj) match_curry = curry_n(match, 2) Теперь мы можем создать проверку типа:
instance_of = lambda type_: match_curry(lambda obj: isinstance(obj, type_)) Тогда для int:
is_int = instance_of(int) print(is_int(2)) # 2 try: is_int('str') except NotMatch: print('not int') # not int Создадим проверку типа для списка, проверяя его каждый элемент:
is_array_of = lambda matcher: match_curry(lambda obj: all(map(matcher, obj))) И тогда для int:
is_array_of_int = is_array_of(is_int) print(is_array_of_int([1, 2, 3])) # 1 2 3 try: is_array_of_int('str') except NotMatch: print('not int') # not int И теперь аналогично для str:
is_str = instance_of(str) is_array_of_str = is_array_of(is_str) Также добавим функцию, возвращающую свой аргумент, идемпотентную =)
identity = lambda x: x print(identity(10)) # 10 print(identity(20)) # 20 И проверку на пустой список:
is_blank = match_curry(lambda xs: len(xs) == 0) print(is_blank([])) # [] try: is_blank([1, 2, 3]) except NotMatch: print('not blank') # not blank Теперь создадим функцию для разделения списка на первый элемент и остаток с применением к ним «проверок»:
def hd_tl(match_x, match_xs, arr): x, *xs = arr return match_x(x), match_xs(xs) hd_tl_partial = lambda match_x, match_xs: partial(hd_tl, match_x, match_xs) И рассмотрим самый простой пример с identity:
hd_tl_identity = hd_tl_partial(identity, identity) print(hd_tl_identity(range(5))) # 0 [1, 2, 3, 4] А теперь с числами:
hd_tl_ints = hd_tl_partial(is_int, is_array_of_int) print(hd_tl_ints(range(2, 6))) # 2 [3, 4, 5] try: hd_tl_ints(['str', 1, 2]) except NotMatch: print('not ints') # not ints А теперь саму функцию, которая будет перебирать все проверки. Она очень простая:
def pattern_match(patterns, args): for pattern, fnc in patterns: try: return fnc(pattern(args)) except NotMatch: continue raise NotMatch(args) pattern_match_curry = curry_n(pattern_match, 2) 
Но зато она неудобна в использовании и требует целый мир скобок, например, нужная нам функция будет выглядеть так:
sum_or_multiply = pattern_match_curry(( (hd_tl_partial(identity, is_blank), lambda arr: arr[0]), # x::[] -> x (hd_tl_ints, lambda arr: arr[0] * sum_or_multiply(arr[1])), # x::xs -> x * sum_or_multiply (xs) где type(x) == int (hd_tl_partial(is_str, is_array_of_str), lambda arr: arr[0] + sum_or_multiply(arr[1])), # x::xs -> x + sum_or_multiply (xs) где type(x) == str )) Теперь проверим ее в действии:
print(sum_or_multiply(range(1, 10))) # 362880 print(sum_or_multiply(['a', 'b', 'c'])) # abc Ура! Оно работает =)
Рекурсия
Во всех классных языках программирования крутые ребята реализуют map через рекурсию, чем мы хуже? Тем более мы уже умеем pattern matching:
r_map = lambda fn, arg: pattern_match(( (hd_tl_partial(identity, is_blank), lambda arr: [fn(arr[0])]), # x::[] -> fn(x) ( hd_tl_partial(identity, identity), lambda arr: [fn(arr[0])] + r_map(fn, arr[1]) # x::xs -> fn(x)::r_map(fn, xs) ), ), arg) print(r_map(lambda x: x**2, range(10))) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] Теперь каррируем:
r_map_curry = curry_n(r_map, 2) twice = r_map_curry(lambda x: x * 2) print(twice(range(10))) try: print(twice(range(1000))) # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] except RuntimeError as e: print(e) # maximum recursion depth exceeded in comparison Что-то пошло не так, попробуем хвостовую рекурсию.
Для этого создадим «проверку» на None:
is_none = match_curry(lambda obj: obj is None) И проверку пары:
pair = lambda match_x, match_y: lambda arr: (match_x(arr[0]), match_y(arr[1])) А теперь и сам map:
def r_map_tail(fn, arg): aux = lambda arg: pattern_match(( (pair(identity, is_none), lambda arr: aux([arr[0], []])), # если аккумулятор None, делаем его [] ( pair(hd_tl_partial(identity, is_blank), identity), lambda arr: arr[1] + [fn(arr[0][0])] # если (x::[], acc), то прибавляем к аккумулятору fn(x) и возвращаем его ), ( pair(hd_tl_partial(identity, identity), identity), lambda arr: aux([arr[0][1], arr[1] + [fn(arr[0][0])]]) # если (x::xs, acc), то делаем рекурсивный вызов с xs и аккумулятором + fn(x) ), ), arg) return aux([arg, None]) Теперь опробуем наше чудо:
r_map_tail_curry = curry_n(r_map_tail, 2) twice_tail = r_map_tail_curry(lambda x: x * 2) print(twice_tail(range(10))) # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] try: print(twice_tail(range(10000))) except RuntimeError as e: print(e) # maximum recursion depth exceeded Вот ведь незадача — python не оптимизирует хвостовую рекурсию. Но теперь на помощь нам придут костыли:
def tail_fnc(fn): called = False calls = [] def run(): while len(calls): # вызываем функцию с аргументами из списка res = fn(*calls.pop()) return res def call(*args): nonlocal called calls.append(args) # добавляем аргументы в список if not called: # проверяем вызвалась ли функция, если нет - запускаем цикл called = True return run() return call Теперь реализуем с этим map:
def r_map_really_tail(fn, arg): aux = tail_fnc(lambda arg: pattern_match(( # декорируем вспомогательную функцию (pair(identity, is_none), lambda arr: aux([arr[0], []])), # если аккумулятор None, делаем его [] ( pair(hd_tl_partial(identity, is_blank), identity), lambda arr: arr[1] + [fn(arr[0][0])] # если (x::[], acc), то прибавляем к аккумулятору fn(x) и возвращаем его ), ( pair(hd_tl_partial(identity, identity), identity), lambda arr: aux([arr[0][1], arr[1] + [fn(arr[0][0])]]) # если (x::xs, acc), то делаем рекурсивный вызов с xs и аккумулятором + fn(x) ), ), arg)) return aux([arg, None]) r_map_really_tail_curry = curry_n(r_map_really_tail, 2) twice_really_tail = r_map_really_tail_curry(lambda x: x * 2) print(twice_really_tail(range(1000))) # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18... Теперь и это заработало =)
Не все так страшно
Если забыть про наш ужасный pattern matching, то рекурсивный map можно реализовать вполне аккуратно:
def tail_r_map(fn, arr_): @tail_fnc def aux(arr, acc=None): x, *xs = arr if xs: return aux(xs, acc + [fn(x)]) else: return acc + [fn(x)] return aux(arr_, []) curry_tail_r_map = curry_2(tail_r_map) И сделаем на нем умножение всех нечетных чисел в списке на 2:
@curry_tail_r_map def twice_if_odd(x): if x % 2 == 0: return x * 2 else: return x print(twice_if_odd(range(10000))) # [0, 1, 4, 3, 8, 5, 12, 7, 16, 9, 20, 11, 24, 13, 28, 15, 32, 17, 36, 19... Получилось вполне аккуратно, хоть медленно и ненужно. Как минимум из-за скорости. Сравним производительность разных вариантов map:
from time import time checker = lambda x: x ** 2 + x limit = 100000 start = time() xs = [checker(x) for x in range(limit)][::-1] print('inline for:', time() - start) start = time() xs = list(map(checker, xs))[::-1] print('map:', time() - start) calculate = curry_tail_r_map(checker) start = time() xs = calculate(xs)[::-1] print('r_map without pattern matching:', time() - start) calculate = r_map_really_tail_curry(checker) start = time() xs = calculate(xs)[::-1] print('r_map with pattern matching:', time() - start) После чего получим:
inline for: 0.010764837265014648
map: 0.010544061660766602
r_map without pattern matching: 4.720803737640381
r_map with pattern matching: 8.376755237579346
Вариант с pattern matching’ом оказался самым медленным, а встроенные map и for оказались самыми быстрыми.
Заключение
Из этой статьи в реальных приложениях можно использовать, пожалуй, только каррирование. Остальное либо нечитаемый, либо тормозной велосипед =)
Все примеры доступны на github.
ссылка на оригинал статьи http://habrahabr.ru/post/193920/
Добавить комментарий