Functional thinking: Thinking functionally, Part 3

In the first and second parts of Functional Thinking, I looked at some of the issues of functional programming, as well as how they relate to Java and its related languages. This part will continue my review, in it I will show the version of the classifier of numbers from the previous parts in the Scala language and discuss some theoretical issues, such as currying , partial application and recursion .

Scala Number Classifier

I saved the Scala version for last as it contains a minimum of mystical syntax, at least for Java programmers. (I recall the requirements for the classifier: you need to classify it as perfect , redundant or insufficient . That number is perfect, whose divisors, except for him, as a divider, are equal to him in the total. insufficient - less.)



Listing 1. Scala classifier

package com.nealford.conf.ft.numberclassifier object NumberClassifier { def isFactor(number: Int, potentialFactor: Int) = number % potentialFactor == 0 def factors(number: Int) = (1 to number) filter (number % _ == 0) def sum(factors: Seq[Int]) = factors.foldLeft(0)(_ + _) def isPerfect(number: Int) = sum(factors(number)) - number == number def isAbundant(number: Int) = sum(factors(number)) - number > number def isDeficient(number: Int) = sum(factors(number)) - number < number } 

Even if you have never seen Scala before this point, this code should be easy to read. As before, we’re interested in the two factors() and sum() . The factors() method takes a list of numbers from 1 to a given number and applies the standard Scala filter() library method to it, using the block of code on the right as a filtering criterion (otherwise called a predicate). In the code block, a special construction is used - implicit parameters * , which allows using the _ symbol instead of the parameter name when there is no need for it. Thanks to the flexibility of the Scala syntax, you can call the filter() method as well as the operator. The construction (1 to number).filter((number % _ == 0)) will also work if you find it more convenient.

')

The sum method uses the left-folding operation already familiar to us (fold left) (implemented in Scala as the foldLeft() method). I don't need names for the parameters in this case, so I use the _ symbol instead of the name, which gives me a simpler and more understandable syntax for the code block. The foldLeft() method does the same as the similarly named method from the Functional Java library, which appeared in the first part:

1. It takes the initial value and combines it with the help of the specified operation with the first element of the list.
2. Takes the result and applies the same operation to the next item in the list.
3. Continues to do this until the list ends.

This is a generalized version of applying such an operation as addition to a list of numbers: start from 0, add the first element, take the result and add the second element to it and continue to the end of the list.

Unit testing

Despite the fact that in the previous version I did not show unit tests, all the examples are tested. A convenient unit testing library is available for Scala - ScalaTest. Listing 2 shows the first test I wrote to test the isPerfect() method from Listing 1:



Listing 2. Unit test for a Scala classifier

 @Test def negative_perfection() { for (i <- 1 until 10000) if (Set(6, 28, 496, 8128).contains(i)) assertTrue(NumberClassifier.isPerfect(i)) else assertFalse(NumberClassifier.isPerfect(i)) } 

However, just like you, I try to learn to think more functionally, so I don’t like the code from listing two for two reasons. First, he himself performs an iteration, this demonstrates the imperative approach to solving the problem. Secondly, the second branch in the if is not really important to me. What problem am I trying to solve? I have to be sure that my classifier does not define the imperfect number as perfect. Listing 3 shows a solution to this problem, but in a slightly different formulation.



Listing 3. Alternate unit test for the Scala number classifier

 @Test def alternate_perfection() { assertEquals(List(6, 28, 496, 8128), (1 until 10000) filter (NumberClassifier.isPerfect(_))) } 

Listing 3 verifies that the list of numbers from 1 to 100 00 that are deemed perfect and the list of known perfect numbers are equal. Functional thinking extends not only your approach to programming, but also how you test your code.

Partial application and currying

The functional approach to filtering lists, which I demonstrated above, is very common among functional languages ​​and libraries. Using code passing as a parameter (in the filter() method in Listing 3) shows a “different” approach to reuse. If you come from the old, design-defining patterns of an object-oriented world, compare this approach with the Pattern Method pattern from the Design Patterns book ** . It defines the algorithm's procurement in the base class, using abstract methods in order to postpone the definition of details until the creation of successors. The functional approach allows you to pass operations as parameters, and apply them appropriately within a method.



Another way to achieve reuse is currying . Named after the mathematician Haskell Curry (the Haskell programming language was also named after him), currying is a transformation of the function of many parameters into a chain of functions of a single parameter. It is closely related to partial application - the technique of fixing the value of one or more arguments of a function leading to the creation of a new function of lower arity. In order to understand the difference between them, let's look at the code in Listing 4, which illustrates currying.



Listing 4. Currying in Groovy

 def product = { x, y -> return x * y } def quadrate = product.curry(4) def octate = product.curry(8) println "4x4: ${quadrate.call(4)}" println "5x8: ${octate(5)} 

In Listing 4, I defined product as a block of code that takes two parameters. Using the built-in groovy curry() method, I use product as the base element to create two new quadrate and octate code blocks. Groovy makes calling code very simple: you can either explicitly call the call () method, or use the syntax sugar provided by the language — a couple of brackets.



Partial application is a more general technique that repeats the curring, but does not limit the resulting function by the number of arguments. Groovy uses the curry() method to implement both techniques as shown in Listing 5:



Listing 5. Comparing partial usage and currying in Groovy using the curry method

 def volume = { h, w, l -> return h * w * l } def area = volume.curry(1) def lengthPA = volume.curry(1, 1) //partial application def lengthC = volume.curry(1).curry(1) // currying println "The volume of the 2x3x4 rectangular solid is ${volume(2, 3, 4)}" println "The area of the 3x4 rectangle is ${area(3, 4)}" println "The length of the 6 line is ${lengthPA(6)}" println "The length of the 6 line via curried function is ${lengthC(6)}" 

The volume code block in Listing 5 calculates the volume of a parallelepiped using a well-known formula. I create a block of area code (which calculates the area of ​​a rectangle) fixing the first volume argument to 1. To use volume as the basis for the block that returns the length of the line, I can use both partial application and currying. lengthPA uses partial application by fixing the first two parameters on the value 1. lengthC applies currying twice to get the same result. The difference is very subtle, and the results are the same, however, if you use the terms currying and partial use as synonyms next to a real functional programmer, you will most likely be shown an error *** .



Functional programming gives you new tools to achieve the same goals as imperative languages. The relationship of these tools is well studied. Earlier, I showed an example of using composition as a reuse tool. So you should not be surprised at the possibility of combining currying and composition. Look at the Groovy code in Listing 6:



Listing 6. Composition and partial use

 def composite = { f, g, x -> return f(g(x)) } def thirtyTwoer = composite.curry(quadrate, octate) println "composition of curried functions yields ${thirtyTwoer(2)}" 

In Listing 6, I create a composite code block that combines two functions. Using this block, I create thirtyTwoer using partial applications in order to combine the two methods together.



Partial application and currying allow you to achieve results similar to mechanisms like the Pattern Method pattern. For example, you can create an incrementer code block by simply completing the adder block as shown in Listing 7:



Listing 7. Finishing functions

 def adder = { x, y -> return x + y } def incrementer = adder.curry(1) println "increment 7: ${incrementer(7)}" 

Scala naturally supports currying, as shown in the example from the documentation in Listing 8:



Listing 8. Currying in Scala

 object CurryTest extends Application { def filter(xs: List[Int], p: Int => Boolean): List[Int] = if (xs.isEmpty) xs else if (p(xs.head)) xs.head :: filter(xs.tail, p) else filter(xs.tail, p) def dividesBy(n: Int)(x: Int) = ((x % n) == 0) val nums = List(1, 2, 3, 4, 5, 6, 7, 8) println(filter(nums, dividesBy(2))) println(filter(nums, dividesBy(3))) } 

The code in Listing 8 demonstrates how to implement the dividesBy() method using the filter() method. I pass the anonymous function to the filter() method, applying the currying method to fix the first dividesBy() parameter on the value used to create this block. When I pass the number to the dividesBy() method, Scala automatically creates a new function using currying.

Recursion filtering

Another concept often associated with functional programming is recursion, which (according to Wikipedia) is “the process of repeating something in a self-similar way”. In computer science, this is a method of repeating an action, consisting in calling a method from oneself (first checking that completion of this series of calls is possible). Often, recursion leads us to a code that is easier to understand, since the solution is based on performing the same operation on a shrinking list of objects.



Look at the filtering list. With an iterative approach, I get the filtering criteria and in a cycle I throw out elements that I don’t want to see at the output. Listing 9 shows a simple implementation of a Groovy filter:



Listing 9. Filtering in Groovy

 def filter(list, criteria) { def new_list = [] list.each { i -> if (criteria(i)) new_list << i } return new_list } modBy2 = { n -> n % 2 == 0 } l = filter(1..20, modBy2) println l 

The filter() method in Listing 9 accepts a list and a selection criterion (code block) as input. Inside it moves through the list by adding the next item to the new list if it meets the criteria.



Let's now go back to Listing 8, which is a recursive implementation of a Scala filter. It follows the standard pattern of functional languages ​​for working with lists. We consider the list as a combination of two elements: the values ​​at the beginning (of the head) and the list of other elements. Many functional languages ​​have special methods for traversing lists using this idiom. The filter() method first checks whether the list is empty - this is a necessary condition for exiting recursion. If the list is empty, then we simply exit the method; if not, we calculate the value of the condition passed as a parameter. If this value is satisfied (which means that this item is to be seen in the list at the output), we return a new list consisting of this element and a filtered list of the remaining elements. If the condition is not fulfilled, then we return the filtered list of the remaining elements (excluding the head). The Scala language list creation operator provides us with good readability and easy perception of both cases.



It seems to me that you are not currently using recursion in principle - it is not included in your toolbox at all. This, however, is largely due to the fact that imperative languages ​​support it weakly, making its application more difficult than it should be. By adding simple syntax and recursion support, functional languages ​​make it another simple way to reuse code.

Conclusion

This part completes my review of the features of the world of functional thinking. Coincidentally, most of this article was about filtering, showing a lot of ways to use and implement it. But it is quite expected. Many functional paradigms are built around lists because programming is often the processing of lists of objects. It is logical to create languages ​​and libraries with powerful tools for working with lists.



In the next part I will tell you more about one of the main concepts of functional programming: immutability.

Notes

* - It seems the author made a mistake here. The _ construct instead of the name of the bound variable in the closure is called the placeholder syntax for anonymous function (Placeholder Syntax for Anonymous Functions), and not the implicit parameter . The implicit parameter is entered by the keyword implicit in the function signature and has a completely different semantics.



** - The Russian translation was formally called “Object-Oriented Design Techniques”. I did not use it in the text, since not many people would recognize the book from it.



*** - The examples in this section look a bit confusing. I advise you to look at the definitions of the terms curring and partial application at the beginning of the section, and not take these examples very seriously.



PS Thank you sndl for the help with the translation and the very idea to do this series.