Functional programming for earthlings - lists

    I continue my short introduction to functional programming. This time we will talk about lists and methods for processing them in a functional style.



    So, the list. Why is so much importance attached to him in the world of AF? The answer to this question lies in the conceptual basis of the Lisp language. A list (in one form or another) is a necessary sematic unit of a programming language. Without a list, we will not be able to get an arbitrary number of information units in the program. On the other hand, adding onlyof lists allows us to implement arbitrarily complex - recursive, even infinite (if the language supports lazy calculations) data structures. List + simple data types is the necessary minimum that any programming language needs. All other complex data types - dictionaries, trees, graphs, etc. - can be implemented using the list.

    So the creators of Lisp decided ... and made a language in which programs are a list:) Yes, any Lisp program is just a list. A function call is a list in which the function name comes first, followed by the argument values. A function definition is a list with the defun keyword first, then the function name, then a nested list with argument names, then a list of operators. Etc. At first glance, this seems rather silly and inconvenient - many have heard reproaches towards Lisp for the incredible amount of brackets (lists there are limited to brackets). But at a second glance ... if the program has such a simplified syntactic structure, then we may well modify the program directly in runtime.

    And for this, Lisp has a macro mechanism - functions whose execution result is re-executed (likeevalin dynamic programming languages, only much more flexible). Thanks to the macro mechanism, Lisp can be changed beyond recognition, you can introduce new syntax and use it. New operators (did you ever want a more convenient form of the loop for? Look at the magnificent, flexible macro forin Common Lisp - this, I am not afraid to say, is a flower in the rough world of loops in forordinary programming languages). Own object system syntactically integrated into the language (look at CLOS - it is also just a set of macros, but it looks like an infusion in the language). Here is such flexibility. Although, of course, you need an editor with highlighting brackets - definitely :)

    Now, let's go back to Lisp with the usual, imperative programming languages ​​- what is the list for us? List processing (arrays, dictionaries) also makes up the lion's share of Python programs. This includes processing the selection of data from the database, and calculating the function to build, and processing the list of files in the file system, and processing the list of lines in the file, as well as much, much more.

    In such languages, we usually process the lists using various kinds of cycles - for, while,do...while. It seems to be not a problem, but the cycle itself is not semantic. Those. he does not say what exactly is being done with the list. We have to read the code of the body of the loop and figure out what it does. The FP represented by Lisp offers us more elegant methods for working with the list (this does not include common list modification operations - sorting, reversing, concatenation, etc.):

    • display ( map ) - a certain function is applied to each element of the list, the result of which is substituted for this element:

    • filtration ( filter ) - each item in the list is checked against the predicate function, and if the item does not match, it is ejected from the list:

    • reduction ( reduce ) - here is a little more complicated. The process is as follows: some basic value and the first element of the list are taken and a reducer function is applied to them; then the result of the action of this function and the second element of the list are taken and the reducer function is applied to them again; then the return value of the function and the third element of the list are taken again - the process repeats until the list ends. The result of the convolution will be one value . For example, this way you can implement the summation of all elements. Or something more complicated (e.g. interpolation, or list inversion). Visually, this can be represented as follows:



    Typically, these three functions come down to most of the problems associated with list processing. But not always. It happens, for example, left-handed and right-handed convolution. There is a need not to filter the list, but to divide it into two parts according to some criterion. Yes, you never know what. The bottom line is that there is a certain function that takes a list as an input and outputs either a list or some simple value at the output, without modifying the original list.

    In Python, the functions described above are present both in the form of functions of the same name, and in the form of syntactic sugar under the strange name list comprehension (I can’t take it correctly, something like comprehending a list ).

    List comprehensions (LC)



    The simplest LC syntax is as follows:

    [expression (a) for a in x]
    


    where xis a list, ais an element of a list, and expression(a)is some expression in which it usually participates a. LC is an expression , and its result is a list. In semantic terms, the above LC corresponds to a function of the mapfollowing form:

    map (lambda a: expression (a), x)
    


    Further, before the very last square bracket, there may still be a branch if:

    [expression (a) for a in x if condition (a)]
    


    As you guessed, this is an analog filter. Using functions, we can rewrite this expression as follows:

    map (lambda a: expression (a), 
      filter (lambda a: condition (a), x))
    


    There is no reducesyntactic analogue, because The main, primary goal of LC is to build lists. It is worth noting one more interesting point: the function mapcan accept several lists. In this case, each time the converter function is called, several arguments will be passed to it: the first argument will be the value of the current element from the first list, the second argument will be the value of the current element of the second list, etc.:

    map (
      lambda a1, a2, a3: a1 + a2 + a3, 
      [1, 2, 3], 
      [4, 5, 6], 
      [7, 8, 9])
    


    In LC, a seemingly similar design is present:

    [expression (a1, a2) for a1 in x1, for a2 in x2]
    


    But alas, this is not the same. The result of this construction will be the Cartesian product of lists that is not very often applied in practice. For example:

    [a1 + a2 for a1 in ['a', 'b', 'c'] for a2 in ['x', 'y']]
    


    => ['ax', 'ay', 'bx', 'by', 'cx', 'cy']


    In practice, LC is convenient to use for simple, non-nested operations, such as obtaining squares of numbers from 1 to 10. In other cases (see the complex example below) it is better to use functions.

    Simple examples



    See the code for all examples of this post below. Let's take a list like this:

    x = [2, 3, 4, 5, 7, 5]
    


    Let's start with something simple; for example, we will square all the elements of the list:

    map (lambda a: a ** 2, x)
    # same thing but with LC
    [a ** 2 for a in x]
    


    => [4, 9, 16, 25, 49, 25]


    Now apply filtering - we filter out all even numbers:

    filter (lambda a: a% 2 == 1, x)
    # same thing but with LC
    [a for a in x if a% 2 == 1]
    


    => [3, 5, 7, 5]


    Now we will combine - we will deduce odd squares of list numbers:

    filter (lambda a: a% 2 == 1, 
      map (lambda a: a ** 2, 
        x))
    # same thing but with LC
    [a ** 2 for a in x if a ** 2% 2 == 1]
    


    => [9, 25, 49, 25]


    As you can see, in the first case, we first display the list, and then filter the result. Now let's play with reduce. To get started, display the sum of all numbers in the list:

    reduce (lambda a, b: a + b, x, 0)
    


    => 26


    The first parameter, as you already understood, is a reducer function (in this case, an adder). The second parameter is our list, and the third is the initial value, or initializer. To show the importance of choosing the right initializer, we give the same example, but for multiplication:

    reduce (lambda a, b: a * b, x, 0)
    


    => 0


    Here we got 0. And rightly so: it turns out, the following expression is satisfied: ((((((((* 0 * 2) * 3) * 4) * 5) * 7) * 5). We fix this example by setting the initializer value to one:

    reduce (lambda a, b: a * b, x, 1)
    


    => 4200


    Now we get the correct value. Now try to get the maximum value from the list:

    reduce (lambda a, b: max (a, b), x)
    


    => 7


    There is no longer an initializer. When the initializer is not specified, reducesubstitutes in its place None. The work of this code is most easily explained visually:



    Finally, we take the task of inverting a list by convolution. Let me remind you that we have a list of numbers 2, 3, 4, 5, 7, 5. The inverted list will be as follows: 5, 7, 5, 4, 3, 2. Let's place the brackets to see what operation we will need to apply in reducer functions: (5, (7, (5, (4, (3, (2)). Obviously, this is the operation of adding each new list item to the beginning of the result from the previous convolution step. The initializer should be an empty list : ( 5, (7, (5, (4, (3, (2, [])). Now we write the specific code:

    reduce (lambda a, b: [b] + a, x, [])
    


    => [5, 7, 5, 4, 3, 2]


    Once again, for clarity, we will display it visually:



    In this post I examined only simple, “non-life” examples of working with lists, but I have a more viable example in stock and I will post it soon in a new post, along with some considerations regarding performance, applicability, about how this is reflected in other areas of computer science, and in general. I hope this will be interesting to someone. For the sim I want to take my leave, thanks for your attention.

    Also popular now: