Geekly Articles each Day
📜 ⬆️ ⬇️

Functional programming for earthlings - functions



In an article about Python, a Xronos user asked to talk about functional programming (FP). Since at one time I had been working quite closely with Lisp, I would like to talk a little bit about it. Just want to say that we are not talking about pure OP. I will talk about simpler and more applicable techniques using the Python language as an example.


')
I will tell you at once why I will not talk about pure OP. A pure FP implies the absence of a computation state and non-modifiable memory (no side effects of executing subroutines). Roughly speaking, the whole program in pure FP is one big formula. Purely imperative concepts, such as a sequence of computations, input-output, and mutable state, are implemented in various beautiful ways, such as Haskell's monads . In addition, the FP includes various concepts of a higher order:



I will not concentrate on this, since a) I myself did not apply these concepts in practice (or applied, but limitedly), b) their applicability to the "ordinary" programmer in "ordinary" languages ​​is not yet available. Therefore, we begin with simpler concepts.

Functions



In the OP, everything is tied around functions, so the function must be an object of the first kind (first-class object) . This means that you can create a function (an anonymous function), you can assign it to a variable, you can pass it to a function, you can return it from a function. Newly created functions must have the closure property - i.e. A new function must capture the surrounding context (declared variables of both local and global scope). A simple example (the full code for this post can be found at the links at the bottom of the post):

 # encoding: utf-8
 def get_writer (type, params):
   # data output in HTML
   def html_writer (filename):
     f = open (filename + '.' + type, 'w');
     f.write ("" "
 <html>
   <head>
     <title>% s </ title>
   </ head>
   <body>
     <h1> Hello </ h1>
   </ body>
 "" "% params ['title'])
     f.close ()
   # data output to PLAIN TEXT
   def text_writer (filename):
     f = open (filename + '.' + type, 'w');
     f.write ("" "
 % s
 =================================

 Hello
 "" ")
     f.close ()
   # determine which data type was requested and return the corresponding function
   if type == 'html':
     return html_writer
   elif type == 'txt':
     return text_writer

 params = {'title': 'Header'}

 # print HTML
 f = get_writer ('html', params)
 f ('file1')
 # we put in PLAIN TEXT
 f = get_writer ('txt', params)
 f ('file2')


Notice that inside html_writer and text_writer , the get_writer ( type and params ) arguments are used. How can this be? After all, after returning from get_writer its arguments, in theory, cease to exist? This is the essence of the closure: if one function returns another, then the so-called context is added to the latter - the set of all available variables (local, global, arguments) with their values ​​at the time of the call. Thus, when returning a function from a function, you return not just a function (sorry for tautology), but a closure - a function + context.

Higher order functions



Now imagine such an example. We are writing a graphing program for certain functions. We define a couple of such functions:

 # encoding: utf-8
 import math

 # y = k * x + b
 def get_linear (k, b):
   return lambda x: k * x + b

 # y = k * x ^ 2 + b

 def get_sqr (k, b):
   return lambda x: k * x ** 2 + b

 # y = A * sin (k * x + phi)
 def get_sin (amplitude, phi, k):
   return lambda x: amplitude * math.sin (math.radians (k * x + phi))

 # y = A * e ^ (k * x)
 def get_exp (amplitude, k, b):
   return lambda x: amplitude * math.exp (k * x + b)


These are simple functions . How can we use them:

 # y = 5 * sin (0.3 * x + 30)
 y = get_sin (5, 30, 0.3)

 # y (90) = 4.19
 print y (90)
 print
 # the result of applying y to the interval from 0 to 180
 print [y (x) for x in range (0, 180)]


But, you see, each of these functions supports the operation of shifting a function along the X axis. But this is a separate function and we can select it! And in the same way, we can single out the scaling functions for X and Y:

 def shifter (func, b):
   return lambda x: func (x + b)

 def x_scaler (func, k):
   return lambda x: func (k * x)

 def y_scaler (func, A):
   return lambda x: A * func (x)

 def combine (func1, func2):
   return lambda x: func2 (func1 (x))


shifter , x_scaler , y_scaler , combine are high-order functions, because they take not only scalar arguments, but also other functions, modifying their behavior. Combine is an extremely useful general function that allows you to apply one function to another. Now we can rewrite our previous functions as follows:

 def identity (x):
   return x

 def sqr (x):
   return x ** 2


Already more interesting. We renamed two functions, and two functions were removed altogether. Why renamed? The fact is that getting rid of the "husk" like scaling and transfer, we got even more general functions. The first one is called identity - the function of identity is a very important concept in the OP. Very important, but very simple - returns its argument and all. The second function simply squares the argument. Now we can get any configuration that we could describe with our functions from the first example by combining simple functions and higher order functions — the main thing is to combine them in the correct sequence. To demonstrate what it means in the correct sequence, I will give the following expression:

 y = x_scaler (shifter (x_scaler (sqr, 5), 6), 7)


What result function will we get? First, the argument is applied ... no, not x_scaler(5) and not sqr , but the outermost x_scaler . Then the shifter . then the internal x_scaler . Then sqr . Twist it a little in your head, you need to get used to it a little. The order is this: the outermost modifier is applied first . The result will be completely analogous to the following function:

 def y (x):
   return sqr (((x * 7) + 6) * 5)


The only difference is that we actually created this function manually in chunks. Now let's try to write to fix y = 5 * sin (0.3 * x + 30):

 # y_scaler (5) should be the most recent
 y = y_scaler (math.sin, 5)
 # 2 last is turning angle to radians
 y = combine (math.radians, y)
 # further - shifter (30)
 y = shifter (y, 30)
 # finally - x_scaler (0.3)
 y = x_scaler (y, 0.3)


Obviously, the result will be completely analogous to the example without combinators.

And the last trick features



Podnatorev in combination, we quite simply write, for example, a modulator of one function with the help of another:

 def modulate (mod, src):
   return lambda x: mod (x) * src (x)


Now we can describe the damped harmonic oscillations:

 # y1 = 5 * sin (15 * x + 30) - the original function
 y1 = \
   x_scaler (
     shifter (
       combine (
         math.radians,
         y_scaler (
           math.sin 
           five)), 
       thirty), 
   15)

 # y2 = exp (-0.01 * x) - modulating function
 y2 = x_scaler (math.exp, -0.01)

 y = modulate (y2, y1)

 print [y (x) for x in range (0, 180)]


In my opinion, not bad:



On this, perhaps, post finish. Next time there will be lists, the map-reduce and list comprehensions techniques as syntactic sugar for this technique and how this all helps us more clearly express our thoughts in the code .

Code for this post: 1 2 3 4

UPDATE: because Karma is now enough, I decided to transfer this topic to the Python blog

Source: https://habr.com/ru/post/49723/

More articles:


All Articles