Jun 9, 2019 / EXERCISE, PROGRAMMING, STYLE

Exercises in Programming Style with higher-order functions

This week, the chapter is named "Kick forward". The style’s constraint is not to call a function directly, but to pass it to the next function as a parameter, to be called later.

This is the 5^th post in the Exercises in Programming Style focus series.Other posts include:

Higher-order functions

I’m not sure whether the concept of higher-order functions has its roots in Functional Programming. However, the concept itself is easy to grasp: a higher-order function can be used as a function parameter - or as a return value - of another function. This is available in Java since version 8, but it’s available in Scala and Kotlin since their beginnings.

In Java, they are mainly used in conjunction with streams:

Stream.of("A", "B", "C", "D", "E")
        .map(new Function<String, String>() {
            @Override
            public String apply(String s) {
                return s.toLowerCase();
            }
        });
    }

Stream.of("A", "B", "C", "D", "E")
      .map(s -> s.toLowerCase());

Stream.of("A", "B", "C", "D", "E")
      .map(String::toLowerCase);

All three previous lines do exactly the same, because lambdas are mapped to anonymous classes of functional interfaces.

In Kotlin, this is pretty similar, but for 2 points:

No Kotlin would ever write an anonymous class, precisely because higher-order functions are available since the beginning
The default parameter name of a lambda is it, just as in Groovy

Stream.of("A", "B", "C", "D", "E")
      .map { it.toLowerCase() }


Stream.of("A", "B", "C", "D", "E")
      .map(String::toLowerCase)

Calling the function

The next logical step once we pass a function to another function is to calling it. In Java, one needs to know the type of the higher-order function. For example, to execute a Function, one needs to call apply() and pass a parameter with the expected type; to execute a Predicate, the function is called test(), etc.

Function<String,String> toLowerCase = String::toLowerCase;
toLowerCase.apply("A");
Predicate<String> isLowerCase = s -> s.equals(s.toLowerCase());
isLowerCase.test("A");

Kotlin is more consistent, as there’s a single function called call(), defined on the KCallable interface.

fun isLowerCase(string: String) = string == string.toLowerCase()
val callable: Boolean = ::isLowerCase.call("A")

However, call() accepts any number of arguments of type Any?. It’s up to the caller to pass the correct number and type for parameters. The following compiles but will fail at runtime:

val callable: KCallable<String> = ::isLowerCase.call("A", 2, Any())

To benefit from the compiler, one can use the KFunctionX type with X being the number of parameters that the function accepts. That type provides an invoke() function with the correct number of arguments and their types.

val ok: KFunction<String, Boolean> = ::isLowerCase.invoke("A")             (1)
val ko: KFunction<String, Boolean> = ::isLowerCase.invoke("A", 2, Any())   (2)

1	Compiles
2	Doesn’t compile

Icing on the cake, invoke() is an operator function which operator is… nothing, so that the following syntax is also valid:

(::isLowerCase)("A")

Applying the theory

In the exercise, the entry-point function calls a function that calls a function, etc. down to 7 nested levels. If we change the KCallable to KFunction, the top function has this very "interesting" signature:

fun readFile(
    filename: String,
    function: KFunction2<
            List<String>,
            KFunction2<
                    List<String>,
                    KFunction2<
                            List<String>,
                            KFunction2<
                                    List<String>,
                                    KFunction2<
                                            List<String>,
                                            KFunction2<
                                                    List<Pair<String, Int>>,
                                                    KFunction1<List<Pair<String, Int>>, Map<String, Int>>,
                                                    Map<String, Int>>,
                                            Map<String, Int>>,
                                    Map<String, Int>>,
                            Map<String, Int>>,
                    Map<String, Int>>,
            Map<String, Int>>
): Map<String, Int>

While I believe that static typing has a lot of benefits, this of course doesn’t make the code easier to read. To cope with that, Kotlin offers type aliases. The following snippet makes use of them to improve the situation:

typealias WordFrequency = Pair<String, Int>
typealias WordFrequencies = List<WordFrequency>
typealias Lines = List<String>
typealias Words = List<String>
typealias MapFunction = KFunction1<WordFrequencies, Map<String, Int>>
typealias SortFunction = KFunction2<WordFrequencies, MapFunction, Map<String, Int>>
typealias FrequencyFunction = KFunction2<Words, SortFunction, Map<String, Int>>
typealias RemoveFunction = KFunction2<Lines, FrequencyFunction, Map<String, Int>>
typealias ScanFunction = KFunction2<Lines, RemoveFunction, Map<String, Int>>
typealias NormalizeFunction = KFunction2<Lines, ScanFunction, Map<String, Int>>
typealias ReadFunction = KFunction2<Lines, NormalizeFunction, Map<String, Int>>

fun readFile(filename: String, function: ReadFunction) = function(read(filename), ::normalize)

Here’s an excerpt of the final code:

fun run(filename: String) = (::readFile)(filename, ::filterChars)                               (1)

fun readFile(filename: String, function: ReadFunction) = function(read(filename), ::normalize)  (2)

fun filterChars(lines: List<String>, function: NormalizeFunction): Map<String, Int> {           (3)
    val pattern = "\\W|_".toRegex()
    val filtered = lines
        .map { it.replace(pattern, " ") }
    return function(filtered, ::scan)                                                           (3)
}

1	Uses the function reference in conjunction with the shortcut operator for `invoke()`. The second parameter is the function reference on the next function to call
2	The second parameter’s type uses an alias, to make the code easier to read. It calls the `invoke()` method of the passed `function` parameter, and pass the next function to call as a reference
3	The rest follows the same logic: use a higher-order function as the last parameter, and call the shortcut version of `invoke()` to continue the chain

Conclusion

As for the introduction, while types are helpful to lower the probability of some bugs, they also decrease readability. Fortunately, Kotlin type aliases are a boon to cope with that.

call() and invoke() are two options to consider when calling functions with reflection. Each of them comes with pros and cons.

The complete source code for this post can be found on Github.

Follow @nicolas_frankel

Exercises in Programming Style with higher-order functions

Higher-order functions

Calling the function

Applying the theory

Conclusion

Composing Exercises in Programming Style

Exercises in Programming Style, recursion