Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Ненормальное функциональное программирование на python

Anna | 16.06.2014 | нет комментариев
Позже просмотра курса 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

Сейчас сделаем функцию для распределения списка на 1-й элемент и остаток с использованием к ним «проверок»:

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.

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB