Python частичное применение функции

Мемоизация и каррирование (Python)

Это способ оптимизации при котором сохраняется результат выполнения функции и этот результат используется при следующем вызове.

Берем рекурсивную реализацию нахождения числа Фибоначчи и смотрим время выполнения.

def clock(func): def clocked(*args, **kwargs): t0 = time.time() result = func(*args, **kwargs) # вызов декорированной функции elapsed = time.time() - t0 name = func.__name__ arg_1st = [] if args: arg_1st.append(', '.join(repr(arg) for arg in args)) if kwargs: pairs = ['%s=%r' % (k, w) for k, w in sorted(kwargs.items())] arg_1st.append(', '.join(pairs)) arg_str = ', '.join(arg_1st) print('[%0.8fs] %s(%s) -> %r' % (elapsed, name, arg_str, result)) return result return clocked 

Время работы будет очень быстро расти при увеличении числа которое нужно найти, плюс возможна ошибка RecursionError.

Для оптимизации подобного алгоритма хорошо подходит метод мемоизации, то есть сохранение и повторное использования ранние вычисленных значений (но с начало конечно нужно постараться вовсе отказаться от рекурсивного алгоритма).

_fib_cache = # ключ - номер числа, значения - число Фибоначчи @clock def mem_fib(n): result = _fib_cache.get(n) if result is None: result = mem_fib(n-2) + mem_fib(n-1) _fib_cache[n] = result return result print('mem_fib(200) =', mem_fib(200)) 

[0.03125453s] mem_fib(200) -> 280571172992510140037611932413038677189525 

def memoize(f): cache = <> def decorate(*args): if args in cache: return cache[args] else: cache[args] = f(*args) return cache[args] return decorate # то же самое через lambda # def memoize(f): # cache = <> # return lambda *args: cache[args] if args in cache else cache.update() or cache[args] # универсальный декоратор для любого количества аргументов # def memoize(f): # cache = <> # # def decorate(*args, **kwargs): # key = (tuple(args), hash(tuple(sorted(kwargs.items())))) # if key not in cache: # cachePython частичное применение функции = f(*args, **kwargs) # return cachePython частичное применение функции # # return decorate @clock @memoize def fib(n): if n < 2: return n return fib(n-2) + fib(n-1) print('fib(20) =', fib(20)) 

И хорошая новость в том, что в стандартной библиотеке functools уже отлично реализован подобный декоратор lru_cache.

LRU расшифровывается как Least Recently Used.

from functools import lru_cache @clock @lru_cache() def fib(n): if n < 2: return n return fib(n-2) + fib(n-1) print('fib(20) =', fib(20)) 

lru_cache имеет два необязательных аргумента.
maxsize — это кол-во хранимых результатов.
typed — при равном true например значения 1 и 1.0 будут считаться разными.

Мемоизация довольно простая и эффективная практика. Благодаря functools.lru_cache, ей удобно пользоваться в Python. Под капотом у нее словарь в виде хэш-таблицы, соответственно ключ должен реализовать хеширование.

Теперь про каррирование или карринг(currying)

Карринг — это преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Мы можем передать часть аргументов в функцию и получить обратно функцию, ожидающую остальные аргументы.

Создадим простую функцию greet, которая принимает в качестве аргументов приветствие и имя:

def greet(greeting, name): print(greeting + ', ' + name) greet('Hello', 'German') 

Небольшое улучшение позволит нам создать новую функцию для любого типа приветствия и передать этой новой функции имя:

def greet_curried(greeting): def greet(name): print(greeting + ', ' + name) return greet greet_hello = greet_curried('Hello') greet_hello('German') greet_hello('Ivan') # или напрямую greet_curried greet_curried('Hi')('Roma') 

А дальше можно сделать это с любым количеством аргументов:

def greet_deeply_curried(greeting): def w_separator(separator): def w_emphasis(emphasis): def w_name(name): print(greeting + separator + name + emphasis) return w_name return w_emphasis return w_separator greet = greet_deeply_curried("Hello")(". ")(".") greet('German') greet('Ivan') 

greet_deeply_curried = lambda greeting: lambda separator: lambda emphasis: lambda name: \ print(greeting + separator + name + emphasis) 

Частичное применение (partial application)

Это процесс применения функции к части ее аргументов.
Другими словами, функция, которая принимает функцию с несколькими параметрами и возвращает функцию с меньшим количеством параметров.

Частичное применение преобразует функцию от n аргументов к (x-n), а карринг создает n функций с 1 аргументов.

Такая возможность есть у Python в стандартной библиотеки functools, это функция
partial.

from functools import partial def greet(greeting, separator, emphasis, name): print(greeting + separator + name + emphasis) newfunc = partial(greet, greeting='Hello', separator=',', emphasis='.') newfunc(name='German') newfunc(name='Ivan') newfunc2 = partial(greet, greeting='Hello', emphasis='.') newfunc2(name='German', separator='. ') newfunc2(name='Ivan', separator='..') 

Еще один пример с partial, решает проблему замыкания в цикле:

from functools import partial def makeActions(): acts = [] for i in range(5): def func(x, y): return x * y acts.append(partial(func, y=i)) # acts.append(partial(lambda x, y: x * y, y=i)) # через lambda # return [partial(lambda x, y: x * y, y=i) for i in range(5)] # через генератор списка return acts for act in makeActions(): print(act(1), end=', ') 

Источник

Пайплайны и частичное применения функций, зачем это в Python

Одно из главных достоинств Python — его выразительность. Функциональные средства языка позволяют лаконично описывать преобразования над данными. На мой взгляд в Python не хватает некоторых инструментов, которые помогли бы удобнее описывать преобразования данных и дополнить функциональную составляющую языка, в частности "пайплайны функций" и их частичное применение. Поэтому в этом посте я лью воду о возможности и необходимости данных средств с экспериментами по их реализации. Пришёл во многом за критикой. Приятного чтения!

Кратко о ФП в Python и почему не хватает пайплайнов на примере

В Python из базовых средств есть довольно удобные map(), reduce(), filter(), лямбда-функции, итераторы и генераторы. Малознакомым с этим всем советую данную статью. В целом это оно всё позволяет быстро и естественно описывать преобразования над списками, кортежами, и тд. Очень часто(у меня и знакомых питонистов) то, что получается однострочник — по сути набор последовательных преобразований, фильтраций, например:
Kata с CodeWars: Найти

Задачка довольно простая, к сожалению(но к счастью для этого поста), решений лучше чем в лоб нет.

def sum_dig_pow(a, b): # range(a, b + 1) will be studied by the function powered_sum = lambda x: sum([v**(i+1) for i,v in enumerate(map(lambda x: int(x), list(str(x))))]) return [i for i in range(a,b+1) if powered_sum(i)==i]

С использованием средств ФП как есть получается скобочный ад "изнутри наружу". Это мог бы исправить пайплайн.

Пайплайны функций

Под сим я подразумеваю такое в идеальном случае (оператор "|" — личное предпочтение):

# f3(f2(f1(x))) f1 | f2 | f3 >> x pipeline = f1 | f2 | f3 pipeline(x) pipeline2 = f4 | f5 pipeline3 = pipeline | pipeline2 | f6 . 

Тогда powered_sum может стать(код не рабочий):

powered_sum = str | list | map(lambda x: int(x), *args) | enumerate | [v**(i+1) for i,v in *args] | sum

Как по мне, такой код легче писать и читать. args в целом выглядят чужеродно. В реальности, не лазя в кишки питона получилось сделать такое(далеко от любых идеалов):

from copy import deepcopy class CreatePipeline: def __init__(self, data=None): self.stack = [] if data is not None: self.args = data def __or__(self, f): new = deepcopy(self) new.stack.append(f) return new def __rshift__(self, v): new = deepcopy(self) new.args = v return new def call_logic(self, *args): for f in self.stack: if type(args) is tuple: args = f(*args) else: args = f(args) return args def __call__(self, *args): if 'args' in self.__dict__: return self.call_logic(self.args) else: return self.call_logic(*args)

Естественно, это один большой костыль, состряпанный ради интереса, даже без kwargs, хотя в похожих случаях и не так важно.

pipe = CreatePipeline() powered_sum = pipe | str | list | (lambda l: map(lambda x: int(x), l)) | enumerate | (lambda e: [v**(i+1) for i,v in e]) | sum

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

Частичное применение функций

Рассмотрим на примере простейшей функции(код не рабочий):

def f_partitial (x,y,z): return x+y+z v = f_partial(1,2) # type(v) = что-нибудь частично применённая функция f_partial, оставшиеся аргументы: ['z'] print(v(3)) # Эквивалент print(f_partial(1,2,3))

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

powered_sum = pipe | str | list | map(lambda x: int(x)) | enumerate | (lambda e: [v**(i+1) for i,v in e]) | sum # map будет вызван ещё раз со вторым аргументом # map(lambda x: int(x))(данные) при вызове

map(lambda x: int(x)) в пайплайне выглядит более лаконично в целом и в терминах последовательных преобразований данных.
Кривенькая неполная реализация на уровне языка:

from inspect import getfullargspec from copy import deepcopy class CreatePartFunction: def __init__(self, f): self.f = f self.values = [] def __call__(self, *args): args_f = getfullargspec(self.f)[0] if len(args) + len(self.values) < len(args_f): new = deepcopy(self) new.values = new.values + list(args) return new elif len(self.values) + len(args) == len(args_f): return self.f(*tuple(self.values + list(args)))

Реализация примера с учётом данного костыля дополнения:

# костыль для обхода поломки inspect над встроенным map m = lambda f, l: map(f, l) # создаём частично применяемую функцию на основе обычной питоньей pmap = CreatePartFunction(m) powered_sum = pipe | str | list | pmap(lambda x: int(x)) | enumerate | (lambda e: [v**(i+1) for i,v in e]) | sum

При более чем двойном вызове в строке(что в целом не особо нужно), придётся уже расставлять скобки, потому что питон подумает, что вызывается аргумент, то есть:

def f (x,y,z): return x+y+z f = CreatePartFunction(f) # работает print(f(1,2,3)) # работает print(f(1,2)(3)) print(f(1)(2,3)) # не работает # 2(3) - int не callable print(f(1)(2)(3)) # работает print((f(1)(2))(3))

Итоги

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

Источник