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.