# Abnormal functional python programming

After looking at the Programming Languages course and reading Functional JavaScript, I wanted to repeat all these cool things in python. Some of the things turned out to be done beautifully and easily, the rest turned out to be scary and unsuitable for use.

The article includes:
• some incomprehensible words;
• currying;
• pattern matching;
• recursion (including tail).

The article is designed for python 3.3+.

### Some confusing words

You can write in python in a functional style, because it has anonymous functions:
``````sum_x_y = lambda x, y: x + y
print(sum_x_y(1, 2))  # 3
``````

Higher-order functions (accepting or returning other functions):
``````def call_and_twice(fnc, x, y):
return fnc(x, y) * 2

print(call_and_twice(sum_x_y, 3, 4))  # 14
``````

Short circuits:
``````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 (almost 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
``````

And cool modules functools and itertools .

## Currying

Преобразование функции от многих аргументов в функцию, берущую свои аргументы по одному.

Consider the simplest case, curry function ``` sum_x_y ``` :
``````sum_x_y_carry = lambda x: lambda y: sum_x_y(x, y)
print(sum_x_y_carry(5)(12))  # 17
``````

Something is not cool at all, try this:
``````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_5(10), sum_with_5(17))  # 15 22
``````

It’s already more interesting, now we’ll make a universal function for currying functions with two arguments, because it ``` lambda x: lambda y: zzzz ``` ’s not cool to write every time ``` lambda x: lambda y: zzzz ``` :
``````curry_2 = lambda fn: lambda x: lambda y: fn(x, y)
``````

And apply it to the function used in real projects ``` 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...
``````

Yes, yes, I used curried ``` map ``` as a decorator and offset the lack of multi-line lambdas.

But not all functions take 2 arguments, so we will make the function ``` curry_n ``` using partial , closures and a little recursion:
``````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=[])
``````

And once again applicable to ``` map ``` , but with 3 arguments:
``````curry_3_map = curry_n(map, 3)
``````

And we’ll make a function to add list items to list items 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
``````

Since ``` curry_2 ``` this is a special case ``` curry_n ``` , you can do:
``````curry_2 = partial(curry_n, n=2)
``````

And for example, apply it to ``` 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 is what I liked the most in sml and the worst in python.
We’ll come up with a goal - to write a function that:
• if it accepts a list of numbers, returns their product;
• if it accepts a list of strings, returns one large concatenated string.

Let's create an auxiliary exception and a function for its “throwing”, which we will use when the comparison does not pass:
``````class NotMatch(Exception):
"""Not match"""

def not_match(x):
raise NotMatch(x)
``````

And a function that does a check and returns an object, or throws an exception:
``````match = lambda check, obj: obj if check(obj) else not_match(obj)
match_curry = curry_n(match, 2)
``````

Now we can create a type check:
``````instance_of = lambda type_: match_curry(lambda obj: isinstance(obj, type_))
``````

Then for ``` int ``` :
``````is_int = instance_of(int)
print(is_int(2))  # 2
try:
is_int('str')
except NotMatch:
print('not int')  # not int
``````

Create a type check for the list, checking each element:
``````is_array_of = lambda matcher: match_curry(lambda obj: all(map(matcher, obj)))
``````

And then for ``` 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
``````

And now similarly for ``` str ``` :
``````is_str = instance_of(str)
is_array_of_str = is_array_of(is_str)
``````

We also add a function that returns its argument, idempotent =)
``````identity = lambda x: x
print(identity(10))  # 10
print(identity(20))  # 20
``````

And check for an empty list:
``````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
``````

Now we will create a function for dividing the list into the first element and the remainder with the use of “checks”:
``````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)
``````

And consider the simplest example with ``` identity ``` :
``````hd_tl_identity = hd_tl_partial(identity, identity)
print(hd_tl_identity(range(5)))  # 0 [1, 2, 3, 4]
``````

And now with the numbers:
``````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
``````

And now the function itself, which will iterate over all the checks. She is very simple:
``````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)
``````

But then it is inconvenient to use and requires a whole world of brackets, for example, the function we need will look like this:
``````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
))
``````

Now check it in action:
``````print(sum_or_multiply(range(1, 10)))  # 362880
print(sum_or_multiply(['a', 'b', 'c']))  # abc
``````

Hooray! It works =)

## Recursion

In all cool programming languages, tough guys implement ``` map ``` through recursion, why are we worse? Moreover, we already know how 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]
``````

Now curry:
``````r_map_curry = curry_n(r_map, 2)
twice = r_map_curry(lambda x: x * 2)
print(twice(range(10)))  # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
try:
print(twice(range(1000)))
except RuntimeError as e:
print(e)  # maximum recursion depth exceeded in comparison
``````

Something went wrong, try tail recursion.
To do this, create a “check” on ``` None ``` :
``````is_none = match_curry(lambda obj: obj is None)
``````

And a couple check:
``````pair = lambda match_x, match_y: lambda arr: (match_x(arr[0]), match_y(arr[1]))
``````

And now himself ``` 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])
``````

Now try out our miracle:
``````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
``````

That's bad luck - python does not optimize tail recursion. But now crutches will come to our aid:
``````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
``````

Now we implement with this ``` 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...
``````

Now it worked =)

## Not so scary

If we forget about our terrible pattern matching, then recursive ``` map ``` can be implemented quite carefully:
``````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)
``````

And make it multiply all the odd numbers in the list by 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...
``````

It turned out quite neatly, albeit slowly and unnecessarily. At least because of speed. Compare the performance of different options ``` map ``` :
``````from time import time

checker = lambda x: x ** 2 + x
limit = 10000
start = time()
xs = [checker(x) for x in range(limit)][::-1]
print('inline for:', time() - start)

start = time()
xs = list(map(checker, range(limit)))[::-1]
print('map:', time() - start)

calculate = curry_tail_r_map(checker)
start = time()
xs = calculate(range(limit))[::-1]
print('r_map without pattern matching:', time() - start)

calculate = r_map_really_tail_curry(checker)
start = time()
xs = calculate(range(limit))[::-1]
print('r_map with pattern matching:', time() - start)
``````

Then we get:
inline for: 0.011110067367553711
map: 0.011012554168701172
r_map without pattern matching: 3.7527310848236084
r_map with pattern matching: 5.926968812942505
The variant with pattern matching turned out to be the slowest, and the built-in map and for turned out to be the fastest.

## Conclusion

From this article in real applications, perhaps, only currying can be used. The rest is either unreadable or a brake bike =)
All examples are available on github.