Abnormal functional python programming

After reviewing the Programming Languages course and reading Functional JavaScript, I wanted to repeat all these cool things in python. Some things turned out to be done beautifully and easily, the rest came out scary and unusable.

The article includes:

• few incomprehensible words;
• currying;
• pattern matching;
• recursion (including tail).

The article is designed for python 3.3+.
')

Few incomprehensible words

In python, you can write 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 

Closures:

 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 of functools and itertools .

Currying

Convert a function from many arguments to a function that takes its arguments one by one.

Consider the simplest case, we curry the 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 

Already more interesting, now let's make a universal function for currying functions with two arguments, because each time writing lambda x: lambda y: zzzz is not at all cool:

 curry_2 = lambda fn: lambda x: lambda y: fn(x, y) 

And apply it to the map function used in real projects:

 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 a curried map as a decorator and this eliminated the lack of multi-line lambda.

But not all functions take 2 arguments, so curry_n 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 we apply to the map , but with 3 arguments:

 curry_3_map = curry_n(map, 3) 

And we will make a function for adding list items with 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 is a special case of curry_n , you can do:

 curry_2 = partial(curry_n, n=2) 

And for example, apply it to the 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

A method for analyzing lists or other data structures for the presence of specified samples.

Pattern matching is what I liked most about sml and worst of all about python.
We will invent our 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

Create an auxiliary exception and a function for its “throwing”, which we will use when the match fails:

 class NotMatch(Exception): """Not match""" def not_match(x): raise NotMatch(x) 

And the function that does the checking and returns the 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 its 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) 

Also add a function that returns its argument, idempotent =)

 identity = lambda x: x print(identity(10)) # 10 print(identity(20)) # 20 

And checking 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 to divide the list into the first element and the remainder, applying “checks” to them:

 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 go through all the checks. It 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 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 let's 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, cool guys implement a map through recursion, why are we worse? Moreover, we are already able to 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 we 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 checking the pair:

 pair = lambda match_x, match_y: lambda arr: (match_x(arr[0]), match_y(arr[1])) 

And now the map itself:

 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 let's try 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 awful pattern matching, then the recursive map can be implemented quite neatly:

 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 we will make on it multiplication of all 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 the speed. Compare the performance of different map options:

 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 get:
inline for: 0.011110067367553711
map: 0.011012554168701172
r_map without pattern matching: 3.7527310848236084
r_map with pattern matching: 5.926968812942505
The pattern matching option was the slowest, and the built-in map and for were the fastest.

Conclusion

From this article in real applications you can only use currying. The rest is either unreadable or brake bike =)
All examples are available on github.