Functional programming for earthlings - functions



    In an article about Python, a Xronos user asked me to talk about functional programming (FP). Since I was pretty busy with Lisp at one time, I would like to talk a little about it. I want to say right away that we are not talking about pure FP. I will talk about simpler and more applicable techniques using the Python language as an example.



    I must say right away why I will not talk about pure AF. Pure FP implies the absence of a computational state and non-modifiable memory (the absence of side effects of subroutine execution). Roughly speaking, the entire program in pure FP is one big formula. Purely imperative concepts, such as a sequence of calculations, input-output and variable state, are implemented in various beautiful ways like monads inHaskell . In addition, various higher-order concepts are included in FIs:

    • pattern matching - like function overloading, only more thoughtful and more flexible
    • continuation (continuation) - the ability to stop the calculation and continue it at another time (ie, "preserve" the state of the calculation and then resume it). We see the type of continuation in the operator’s workyield
    • lazy calculations - With this model, roughly speaking, the arguments of functions are calculated only when they are really necessary, and not when entering the function
    • algebraic data types, recursive data types, automatic type inference - etc. etc.


    I will not concentrate on this, because a) I myself did not apply these concepts in practice (or applied them, but to a limited extent), b) their applicability to the “ordinary” programmer in “ordinary” languages ​​is not yet available. Therefore, we will start with simpler concepts.

    Functions



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

    # encoding: utf-8
    def get_writer (type, params):
      # HTML output
      def html_writer (filename):
        f = open (filename + '.' + type, 'w');
        f.write ("" "
    
      
        %s

    Hello

    "" "% params ['title']) f.close () # data output to PLAIN TEXT def text_writer (filename): f = open (filename + '.' + type, 'w'); f.write ("" " % s =================================== Hello "" ") f.close () # define what data type was requested and return the corresponding function if type == 'html': return html_writer elif type == 'txt': return text_writer params = {'title': 'Header'} # output to HTML f = get_writer ('html', params) f ('file1') # output to PLAIN TEXT f = get_writer ('txt', params) f ('file2')


    Pay attention to what is inside html_writerand text_writerused the arguments get_writer( typeand params). How can this be? After all, after returning from get_writerher 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 totality 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 the tautalogy), 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 pair 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
    # 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 the function along the X axis. But this is a separate function and we can select it! And in the same way, we can distinguish the scaling functions along 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- a higher-order function (high-order functions), as they accept not only scalar arguments, but also other functions, modifying their behavior. Combine- 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 altogether removed. Why renamed? The fact is that having got rid of the “husk” like scaling and transfer, we got even more general functions. The first of them is called identity- identity function - a very important concept in FP. Very important, but very simple - returns its argument and all. The second function simply squares the argument. Now, any configuration that we could describe with our functions from the first example, we can get 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 quote this expression:

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


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

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


    With the only difference, we actually created this function manually in pieces. Now let's try to write y = 5 * sin (0.3 * x + 30) to fix it:

    # the most recent should apply y_scaler (5)
    y = y_scaler (math.sin, 5)
    # penultimate - turning an angle into 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 feint features



    Having become skilled in combining, we will quite simply write, for example, a modulator of one function using 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) - original function
    y1 = \
      x_scaler (
        shifter (
          combine (
            math.radians,
            y_scaler (
              math.sin, 
              5)), 
          thirty), 
      fifteen)
    # 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, the post will end. Next time there will be lists, the map-reduce technique and list comprehensions as syntactic sugar for this technique and how it all helps us to express our thoughts more clearly in the code .

    Code for this post: 1 2 3 4

    UPDATE: since now there is enough karma, I decided to transfer this topic to the Python blog

    Also popular now: