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

[s2002kir]

Я слышал про присутствие функционального стиля в python и теперь в этом убедился. Спасибо.

[IIvana]

Факториал и Фибоначчи — близнецы-братья.
Кто более матери-истории ценен?
Мы говорим Факториал — подразумеваем (и далее по тексту классика)

[longclaps]

Я открыл, что Китай и Испания совершенно одна и та же земля, и только по невежеству считают их за разные государства. Я советую всем нарочно написать на бумаге Испания, то и выйдет Китай.
Н.В.Гоголь, «Записки сумасшедшего»

[sanyaa]

Ваша функция называется factorial, а вычисляет числа Фибоначчи.

В остальном поддерживаю вас и статью. Будет интересно, если продолжите и расскажите о других способах оптимизации, о применении мемоизации, например, в динамическом программировании и т.д.

[comratvlad]

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

[justwack]

Я мог бы написать, что это был тест на внимательность, но нет…
Названия функций исправил. Всем спасибо!

[longclaps]

Это, безусловно, тест на внимательность:

print('200! =', mem_fib(200))

[peleron]

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

[ptitca_zu]

С использованием lru_cache можно еще написать синглтон «для ленивых»:

from functools import lru_cache

@lru_cache(maxsize=None)
class S: pass

[PavelMSTU]

У меня пятничный утренний неunderstand.
Поясните, пж!

[ptitca_zu]

If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound

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

[saluev]

Как это связано? Если конструктор без аргументов, нужен кэш размера 1.

[ptitca_zu]

Согласен, что для конструктора без аргументов достаточно кеша размера 1.
None будет работать для конструктора с любым количеством аргументов.

Нужно еще оговориться, что так ни в коем случае не нужно писать синглтоны, конечно.

[Sly_tom_cat]

Memorize/lru_cashe — вещь понятная(понятно для чего).
А вот в чем смысл картирование — не совсем понял к чему применит можно...?

[torkve]

Вообще, partial в питоне — это не каррирование, а частичное применение, это разные вещи.
Например, вот каррирование в OCaml:

# let add x y = x + y;;
val add : int -> int -> int = <fun>
# let add2 = add 2;;
val add2 : int -> int = <fun>
# let sum = add2 3;;
val sum : int = 5

А вот частичное применение в питоне:

>>> add = lambda x, y: x + y
>>> add    
<function <lambda> at 0x7f78aba64aa0>
>>> add2 = partial(add, 2)
>>> add2 
<functools.partial object at 0x7f78aba57520>
>>> sum = partial(add2, 3)
>>> sum
<functools.partial object at 0x7f78aba577e0>
>>> sum()
5

Т.е. мы получаем всё ещё функцию, а не результат, более того, мы можем навесить ещё один partial с какими-нибудь аргументами на функцию sum и узнаем об ошибке только в момент вызова полученной новой функции.

А нужно это во многих местах: например, если у какого-нибудь объекта (кнопки, сокета, whatever) подписка на событие требует передать функцию-обработчик, принимающую один аргумент, например, событие, а у вас более сложный обработчик, которому вы хотите передавать больше информации:

def complex_handler(obj, logger_name, times_to_log, event):
    for _ in range(times_to_log):
        logging.getLogger(logger_name).info("got event from %s: %s", obj, event)
obj1.subscribe(partial(complex_handler, obj1, "incoming", 3))
obj2.subscribe(partial(complex_handler, obj2, "outgoing", 5))

[justwack]

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

[justwack]

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

[maxfox]

По личному опыту — partial полезен там, где есть работа с callback'ами. Т.е. некий API хочет получить от вас функцию, чтобы потом ее использовать, а у вас уже и функция готовая есть, но беда в том, что ей нужны аргументы. А модуль, принимающий вашу функцию, этих аргументов ей не передает. Тут нас выручает partial, он как-бы фиксирует значения некоторого количества аргументов (на самом деле, создает обертку вокруг вашей функции). Если вам не нужно работать с callback'ами, то скорее всего и partial не пригодится.
Да, и как уже отметили выше, каррирование (carrying) и частичное применение (partial application) — это разные вещи.

[Sinn3r]

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

Примеры

На питоне

def sqr(arg): return arg * arg
def is_even(arg): return arg % 2 == 0
xs = range(1, 4)
list(map(sqr, filter(is_even, xs)))
>>> [4, 16]

Не на питоне, все функции каррированы

let sqr = arg * arg
let is_even arg = arg % 2 == 0
xs = range 4
list map sqr filter is_even xs
// или с пайп оператором
list_of_squared_even xs = xs |> filter is_even |> map sqr |> list

Если читать справа налево то даже читаемо

То же самое, но подробней

let sqr = arg * arg
let is_even arg = arg % 2 == 0
xs = range 1 4

each_square = map sqr  # -> returns func<iterable, iterable>
filter_even = filter is_even  # -> returns func<iterable, iterable>
list_of_squared_even = each_square filter_even # -> returns func<iterable, iterable>
list_of_squared_even xs
>>> [4, 16]

Если не ошибаюсь так работает F#, поправьте если не прав

[Dron_Dronych]

Не хватает результатов выполнения функций. Было бы удобнее. В целом: спасибо за статью.

[stahh]

В последнем примере у вас не генератор, а генерация списка. Генератор будет выглядеть примерно так:

def makeActions():
    acts = []
    for i in range(5):
        def func(x, y):
            return x * y
        yield partial(lambda x, y: x * y, y=i)

[justwack]

Речь про list comprehension, если не ошибаюсь в русской терминологии это списковое включение/абстракция списков/генерация списков/генератор списка.

Решение через генераторы:

def generator_expression():
    return (lambda x: x * i for i in range(5))

def generator():
    for i in range(5):
        yield lambda x: x * i