Functional programming for earthlings - lists

I continue my little introduction to functional programming. This time it will be about lists and methods of processing them in a functional style.



So, the list. Why is it so important in the world of FP? The answer to this question lies in the conceptual basis of the Lisp language. A list (in one form or another) is a necessary semantic unit of a programming language. Without a list, we will not be able to get an arbitrary amount of information in the program. On the other hand, adding only lists allows us to implement arbitrarily complex - recursive, even infinite (if there is support for lazy calculations in the language) - data structures. The list + simple data types is the minimum necessary that any programming language needs. All other complex data types - dictionaries, trees, graphs, etc. - can be implemented using a list.
')
So the creators of Lisp decided ... and made a language in which the 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. The function definition is the list in which the defun keyword first appears, then the name of the function, then the nested list with the names of the arguments, then the list of statements. And so on. At first glance, this seems rather stupid and inconvenient - many have heard accusations towards Lisp for an incredible amount of brackets (lists there are limited to brackets). But at a second glance ... if a program has such a simplified syntactic structure, then we can easily modify the program directly in runtime.

And for this, Lisp has a macro mechanism — functions whose execution is re-executed (like eval in dynamic programming languages, but much more flexible). Thanks to the macro mechanism, Lisp can be changed beyond recognition, you can enter a new syntax and use it. New operators (would you like sometime more convenient form of a for loop? Look at the magnificent, flexible for for Common Lisp macro - I’m not afraid to say, a flower in the rough world of for loops for ordinary programming languages). Its object system, syntactically embedded in the language (look at CLOS - this is also just a set of macros, and it looks in the language as merged). Here is such a flexibility. Although, of course, you need an editor with highlighting brackets - sure :)

Now back from Lisp to ordinary, imperative programming languages ​​- what's the list for us here? Processing lists (arrays, dictionaries) also makes up the lion's share of Python programs. This includes processing a sample of data from a database, calculating a function for building, processing a list of files in a file system, processing a list of strings in a file, and much, much more.

In such languages, we usually process lists using various kinds of cycles - for , while , do...while . This is not a problem, as it were, 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 loop body and parse what it does. The OP in the face of Lisp offers us more elegant methods of working with a list (this does not include the common list modification operations - sorting, converting, concatenating, etc.):

• mapping ( map ) - a certain function is applied to each element of the list, the result of which is substituted instead of this element:
  
  
• filtering ( filter ) - each element of the list is checked for compliance with the function-predicate, and if the element does not match, it is thrown out of the list:
  
  
• convolution ( reduce ) is a bit more complicated here. The process is as follows: a certain base value and the first element of the list are taken and a gearing 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 function reducer is applied to them again; then the return value of the function and the third element of the list are taken again - the process is repeated until the list ends. The result of the convolution is one value . For example, in this way you can implement the summation of all elements. Or something more complicated (for example, interpolation, or list inversion). Visually, this can be represented as:
  
  

Usually, these three functions reduce most of the problems associated with list processing. But not always. It happens, for example, left-side and right-side convolution. It may be necessary not to filter the list, but to divide it according to some attribute into two parts. But you never know what. The bottom line is that there is a certain function that accepts a list as input and outputs either a list or some simple value as 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 will not undertake to translate correctly, something like a list comprehension ).

List comprehensions (LC)

The simplest syntax for LC is:

 [expression (a) for a in x]

where x is a list, a is a list element, and expression(a) is some expression in which a usually participates. LC is an expression , and its result is a list. In terms of meaning, the above described LC corresponds to the map function of the following form:

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

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

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

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

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

There is no syntactic analogue for reduce , since The primary, primary goal of LC is the construction of lists. It is worth noting another interesting point: the map function can take multiple lists. In this case, each time the converter function is called, it will be passed several arguments: 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, and so on:

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

There seems to be a similar construction in LC:

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

But alas, it is not the same. The result of the action of this construction will be a Cartesian product of lists that is not too often used 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 conveniently used 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

Code for all examples of this post, see below. Let's take the following list:

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

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

 map (lambda a: a ** 2, x)

 # same, but with LC
 [a ** 2 for a in x]

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

Now we apply filtering - we will exclude all even numbers:

 filter (lambda a: a% 2 == 1, x)

 # same, but with LC
 [a for a in x if a% 2 == 1]

=> [3, 5, 7, 5]

Now we combine - we will display odd squares of numbers in the list:

 filter (lambda a: a% 2 == 1, 
   map (lambda a: a ** 2, 
     x))

 # same, 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 begin with, we derive the sum of all the numbers in the list:

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

=> 26

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

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

=> 0

Here we got 0. And it’s right: it turns out that the following expression is executed: ((((((0 * 2) * 3) * 4) * 5) * 7) * 5). 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 let's try to get the maximum value from the list:

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

=> 7

There is no initializer here. When the initializer is not specified, reduce replaces None in its place. The work of this code is easiest to explain visually:



Finally, take the task of inverting the list by means of 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 arrange brackets to see what operation we 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 must 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, let's display visually:



In this post, I looked at only simple, "non-life" examples of working with lists, but I have a viable example in stock, and I will post it in the near future in a new post, along with some considerations about performance, applicability, what this is reflected in other areas of computer science, and in general. I hope it will be interesting to someone. For this I want to bow out, thank you for your attention.