Why functional programming?
Functional programming has been around for almost as long as other programming paradigms, such as procedural and object-oriented programming, if not longer. But in the past 10 years, it has gained major momentum. The reason for that is because something else stalled: CPU speeds. We cannot speed up our CPUs as much as we did in the past, so we must parallelize our programs. And it turns out that the functional programming paradigm is exceptional at running parallel tasks. The evolution of multicore processors is a very interesting topic by itself, but we'll be able to cover it only briefly. Workstations had multiple processors since the 1980s at least, to support running tasks from different users in parallel. Since workstations were huge anyway, they didn't need to worry about cramming everything into one chip. But with multiprocessors coming to the consumer market around 2005, it was necessary to have one physical unit that could do work in parallel. That's the reason we have multiple cores on one chip in our PC or laptop.
But that's not the only reason some swear by functional programming. Here are a few more:
Functional programming favors pure functions, and pure functions are usually easier to reason about and to test
Code written in a functional way is often more declarative than imperative, dealing with the what and not the how
We have extensively studied functional programming, and anyone working in Android app development and as a Kotlin developer for back-end frameworks like Ktor knows the significant advantages that functional programming offers compared to procedural programming languages.
Immutability
One of the key concepts of functional programming is immutability. It means that from the moment the function receives input to the moment the function returns output, the object doesn't change. How could it change, you wonder? Let's see a simple example: fun <T> printAndClear(list: MutableList<T>) {
for (e in list) {
println(e)
list.remove(e)
}
}
printAndClear(mutableListOf("a", "b", "c")) The output would be first "a", then we'll receive ConcurrentModificationException. Wouldn't it be great if we could protect ourselves from such runtime exceptions in the first place?
Tuples
In functional programming, a tuple is a piece of data that cannot be changed after it is created. One of the most basic tuples in Kotlin is Pair: val pair = "a" to 1 Pair contains two properties, first and second, and is immutable: pair.first = "b" // Doesn't work
pair.second = 2 // Still doesn't We can destructure a Pair into two separate values: val (key, value) = pair
println("$key => $value") When iterating over a map, we receive another tuple, Map.Entry: for (p in mapOf(1 to "Sunday", 2 to "Monday")) {
println("${p.key} ${p.value}")
}
In general, data classes are usually a good implementation for tuples. But, as we'll see in the Value Mutation section, not every data class is a proper tuple.
Value mutation
In our earlier blog game we design as Maronic, we would like to count the average score over one thousand games. For that, we have the following
data class: data class AverageScore(var totalScore: Int = 0,
var gamesPlayed: Int = 0) {
val average: Int
get() = if (gamesPlayed <= 0)
0
else
totalScore / gamesPlayed
}
We were smart: we protected ourselves from any invalid output by checking for divisions by zero. But what will happen when we write the following code?
val counter = AverageScore()
thread(isDaemon = true) {
while(true) counter.gamesPlayed = 0
}
for (i in 1..1_000) {
counter.totalScore += Random().nextInt(100)
counter.gamesPlayed++
println(counter.average)
}
Soon enough, you'll receive ArithmeticException anyway. Our counter somehow becomes zero. If you want your data classes to be immutable, be sure to specify all their properties as val (values), and not var (variables).
Immutable collections
I think that our junior developer learned their lesson. Instead, they produced this code, which is not very efficient, but which gets rid of those variables:
data class ScoreCollector(val scores: MutableList<Int> = mutableListOf())
val counter = ScoreCollector()
for (i in 1..1_000) {
counter.scores += Random().nextInt(100)
println(counter.scores.sumBy { it } / counter.scores.size)
}
But the maleficent thread strikes again:
thread(isDaemon= true, name="Maleficent") {
while(true) counter.scores.clear()
}
We again receive ArithmeticException.It's not enough that your data class contains only values. If its value is a collection, it must be immutable in order for the data class to be considered immutable. The same rule is applied to classes contained within other data classes:
data class ImmutableScoreCollector(val scores: List<Int>)
Now the maleficent thread cannot even call clear() on this collection. But how should we add scores to it? One option is to pass the entire list in the constructor:
val counter = ImmutableScoreCollector(List(1_000) {
Random().nextInt(100)
})
Functions as values
We already covered some of the functional capabilities of Kotlin to our earlier blog in Design Patterns. The Strategy and Command design patterns are but a few that heavily rely on the ability to accept functions as arguments, return functions, store them as values, or put them inside collections. In this section, we'll cover some other aspects of functional programming in Kotlin, such as function purity and currying.
Higher-order functions
As we discussed previously, in Kotlin, it's possible for a function to return another function:
fun generateMultiply(): (Int, Int) -> Int {
return { x: Int, y: Int -> x * y}
}
Functions can also be assigned to a variable or value to be invoked later on:
val multiplyFunction = generateMultiply()
...
println(multiplyFunction(3, 4))
The function assigned to a variable is usually called a literal function. It's also possible to specify a function as a parameter:
fun mathInvoker(x: Int, y: Int, mathFunction: (Int, Int) -> Int) {
println(mathFunction(x, y))
}
mathInvoker(5, 6, multiplyFunction) If a function is the last parameter, it can also be supplied ad hoc, outside of the brackets: mathInvoker(7, 8) { x, y ->
x * y
}
In general, a function without a name is called an anonymous function. If a function without a name uses short syntax, it's called a lambda: val squareAnonymous = fun(x: Int) = x * x
val squareLambda = {x: Int -> x * x}
Pure functions
A pure function is a function without any side effects. Take the following function, for example:
fun sayHello() {
println("Hello")
}
How do you test to see whether "Hello" is indeed printed? The task is not as simple as it seems, as we'll need some means to capture the standard output, the same console where we usually see stuff printed. Compare it to the following function: fun hello() = "Hello" The following function doesn't have any side effects. That makes it a lot easier to test:
fun testHello(): Boolean {
return "Hello" == hello()
}
Does the hello() function look a bit meaningless to your eyes? That's actually one of the properties of pure functions.
Their invocation could be replaced by their result (if we knew all their results, that is). This is often called referential transparency. Not every function written in Kotlin is pure:
fun <T> removeFirst(list: MutableList<T>): T {
return list.removeAt(0)
}
If we call the function twice on the same list, it will return different results:
val list = mutableListOf(1, 2, 3)
println(removeFirst(list)) // Prints 1
println(removeFirst(list)) // Prints 2 Try this one: fun <T> withoutFirst(list: List<T>): T {
return ArrayList(list).removeAt(0)
}
Now our function is totally predictable, no matter how many times we invoke it: val list = mutableListOf(1, 2, 3)
println(withoutFirst(list)) // It's 1
println(withoutFirst(list)) // Still 1
As you can see, we used an immutable interface this time, List<T>, which helps us by preventing even the possibility of mutating our input. Together with immutable values from the previous section, pure functions provide a very strong tool that allows easier testing by providing predictable results and parallelization of our algorithms.
Currying
Currying is a way to translate a function that takes a number of arguments into a chain of functions that each take a single argument. This may sound confusing, so let's look at a simple example:
fun subtract(x: Int, y: Int): Int {
return x - y
}
println(subtract(50, 8))
This is a function that returns two arguments. The result is quite obvious. But maybe we would like to invoke this function with the following syntax instead: subtract(50)(8) We've already seen how we can return a function from another function:
fun subtract(x: Int): (Int) -> Int {
return fun(y: Int): Int {
return x - y
}
}
Here it is in the shorter form: fun subtract(x: Int) = fun(y: Int): Int {
return x + y
}
And here it is in an even shorter form: fun subtract(x: Int) = {y: Int -> x - y} Although not very useful by itself, it's still an interesting concept to grasp. And if you're a JavaScript developer looking for a new job, make sure you understand it really well, since it's being asked about in nearly every interview.
Memorization
If our function always returns the same output for the same input, we could easily map between previous input and output, and use it as a cache. That technique is called memoization:
class Summarizer {
private val resultsCache = mutableMapOf<List<Int>, Double>()
fun summarize(numbers: List<Int>): Double {
return resultsCache.computeIfAbsent(numbers, ::sum)
}
private fun sum(numbers: List<Int>): Double {
return numbers.sumByDouble { it.toDouble() }
}
}
We use a method reference operator, ::, to tell computeIfAbsent to use the sum() method in the event that input wasn't cached yet. Note that sum() is a pure function, while summarize() is not. The latter will behave differently for the same input. But that's exactly what we want in this case: val l1 = listOf(1, 2, 3)
val l2 = listOf(1, 2, 3)
val l3 = listOf(1, 2, 3, 4)
val summarizer = Summarizer()
println(summarizer.summarize(l1)) // Computes, new input
println(summarizer.summarize(l1)) // Object is the same, no compute
println(summarizer.summarize(l2)) // Value is the same, no compute
println(summarizer.summarize(l3))
Computes The combination of immutable objects, pure functions, and plain old classes provides us with a powerful tool for performance optimizations. Just remember, nothing is free. We only trade one resource, CPU time, for another resource, memory. And it's up to you to decide which resource is more expensive for you in each case.
Expressions,
expressions not statements A statement is a block of code that doesn't return anything. An expression, on the other hand, returns a new value. Since statements produce no results, the only way for them to be useful is to mutate state. And functional programming tries to avoid mutating the state as much as possible. Theoretically, the more we rely on expressions, the more our functions will be pure, with all the benefits of functional purity. We've used the if expression many times already, so one of its benefits should be clear: it's less verbose and, for that reason, less error-prone than the if statement. Pattern matching The concept of pattern matching is like switch/case on steroids for someone who comes from Java. We've already seen how when expression can be used, in Chapter 1, Getting Started with Kotlin, so let's briefly discuss why this concept is important for the functional paradigm. As you may know, switch in Java accepts only some primitive types, strings, or enums. Consider the following code in Java:
class Cat implements Animal {
public String purr() {
return "Purr-purr";
}
}
class Dog implements Animal {
public String bark() {
return "Bark-bark";
} }
interface Animal {}
If we were to decide which of the functions to call, we would need something like this:
public String getSound(Animal animal) {
String sound = null;
if (animal instanceof Cat) {
sound = ((Cat)animal).purr();
}
else if (animal instanceof Dog) {
sound = ((Dog)animal).bark();
}
if (sound == null) {
throw new RuntimeException();
}
return sound;
}
This method could be shortened by introducing multiple returns, but in real projects, multiple returns are usually bad practice. Since we don't have a switch statement for classes, we need to use an if statement instead. Compare that with the following Kotlin code:
fun getSound(animal: Animal) = when(animal) {
is Cat -> animal.purr()
is Dog -> animal.bark()
else -> throw RuntimeException()
}
Since when is an expression, we avoided the intermediate variable altogether. But what's more, using pattern matching, we can also avoid most of the code that concerns type checks and casts. Recursion Recursion is a function invoking itself with new arguments:
fun sumRec(i: Int, numbers: List<Int>): Long {
return if (i == numbers.size) {
0
} else {
numbers[i] + sumRec(i + 1, numbers)
}
}
We usually avoid recursion, due to Stack Overflow error that we may receive if our call stack is too deep. You can call this function with a list that contains a million numbers to experience it:
val numbers = List(1_000_000) {it}
println(sumRec(0, numbers)) // Crashed pretty soon, around 7K
One of the great benefits of tail recursion is that it avoids the dreaded stack overflow exception. Let's rewrite our recursive function using a new keyword, tailrec, to avoid that problem:
tailrec fun sumRec(i: Int, sum: Long, numbers: List<Int>): Long {
return if (i == numbers.size) {
return sum
} else {
sumRec(i+1, numbers[i] + sum, numbers)
}
}
Now the compiler will optimize our call and avoid exception completely. Summary You should now have a better understanding of functional programming and its benefits. We've discussed the concepts of immutability and pure functions. A combination of the two often results in more testable code, which is easier to maintain. Currying and memoization are two useful patterns that originate from functional programming. Kotlin has a tailrec keyword that allows the compiler to optimize tail recursion. We also looked at higher-order functions, expressions versus statements, and pattern matching. In the next chapter, we'll put this knowledge to practical use, and discover how reactive programming builds upon functional programming in order to create scalable and resilient systems.
Streaming Your Data
For Java developers, they first appeared in Java 8 with the introduction of Stream API. But they were around for much longer in functional languages. First, since we expect that many of our readers are familiar with Java 8, let's cover what Stream API is in Java briefly. Streams from Java8 are not to be confused with some of the I/O classes with similar names, such as InputStream or OutputStream. While the latter represent data, the former are sequences of elements of the same type. If those are sequences, and they all have the same type, how are they different from Lists? Well, streams can be infinite, unlike collections. There is also a set of actions defined for Java streams. Not only are those actions the same for any kind of stream,
they also have familiar names for those that come from totally different languages. There's the map() function in JavaScript, which does the same as the map() method in Java. The idea of making extensive use of small, reusable, and composable functions comes directly from functional programming, which we discussed in the previous chapter. They allow us to write code in a manner that tells what we want to do, instead of how we want to do it. But in Java, to use those functions, we have to either receive a stream or create a stream from a collection. In Java, in order to get to all this functional goodness for collections, we can do the following:
Arrays.asList("a", "b", "c") // Initialize list
.stream() // Convert to stream
.map(...) // Do something functional here
.toList() // Convert back to list In Kotlin, you can do the same: listOf("a", "b", "c").stream().map{...}.toList()
But all those methods and more are available directly on collections: listOf("a", "b", "c").map(...)
That's all; there is no need to convert from the stream and back unless you plan to operate on infinite data in the first place. Of course, it's not as simple as that, but we cover the differences and pitfalls near the end of this chapter, in the Streams are lazy, collections are not section. Let's start by understanding what those weird functions actually do. In this chapter, we won't be able to cover all the functions available on collections, but we'll cover the most widely used ones. The examples will be somewhat boring, mostly lists of numbers, letters, and people. That's to let you focus on how each function actually works.
The it notation
We glanced at the notion of it briefly in previous chapters, but for this chapter, we need to understand it a bit more (pun intended). Kotlin is all about brevity. First, if our lambda doesn't have an argument, we don't need to specify anything:
val noParameters = { 1 } // () -> Int
implicitly But what if we have a function that takes another function as an argument (and doesn't do anything with it for simplicity)? See the following code:
fun oneParameter(block: (Int)->Long){ }
We can specify both the argument name and type explicitly, and wrap them in brackets, like any other function invocation:
val oneParameterVeryVeryExplicit = oneParameter( {x: Int -> x.toLong() })
But since the lambda is the last parameter (and the only one, in this case), we can omit the brackets:
val oneParameterVeryExplicit = oneParameter {x: Int -> x.toLong() }
And since the compiler can infer the type of parameter, we can omit it too:
val oneParameterExplicit = oneParameter {x -> x.toLong() }
And since x is the only parameter, we can use the implicit name for it, which is it:
val oneParameterImplicit = oneParameter { it.toLong() }
We'll use the shortest notation in most of the following examples.
Filter family
Another common task is filtering a collection. You know the drill. You iterate over it and put only values that fit your criteria in a new collection. For example, if given a range of numbers between 1-10, we would like to return only odd ones. Of course, we've already learned this lesson from the previous example, and wouldn't simply create a function called filterOdd(), as later we would be required to also implement filterEven(), filterPrime(), and so on. We'll receive a lambda as the second argument right away: fun filter(numbers: List<Int>, check: (Int)->Boolean): MutableList<Int> {
val result = mutableListOf<Int>()
for (n in numbers) {
if (check(n)) {
result.add(n)
}
}
return result
}
Invoking it will print only odd numbers. How odd: println(filter((1..10).toList()) {
it % 2 != 0
})
// [1, 3, 5, 7, 9] And, of course, we have a built-in function that does exactly that already:
println((1..10).toList().filter {
it % 2 != 0
})
Find family Say you have an unordered list of objects:
data class Person(val firstName: String,
val lastName: String,
val age: Int)
val people = listOf(Person("Jane", "Doe", 19),
Person("John", "Doe", 24),
Person("John", "Smith", 23)) And would like to find a first object that matches some criteria. Using extension functions, you could write something like this:
fun <T> List<T>.find(check: (T) -> Boolean): T? {
for (p in this) {
if (check(p)) {
return p
}
}
return null
}
And then, when you have a list of objects, you can simply call find() on it:
println(people.find {
it.firstName == "John"
}) // Person(firstName=John, lastName=Doe)
Luckily, you don't have to implement anything. This method is already implemented for you in Kotlin. There's also an accompanying findLast() method, which does the same, but which starts with the last element of the collection:
println(people.findLast {
it.firstName == "John"
}) // Person(firstName=John, lastName=Smith)
Drop family OK,
this is cool if you have to iterate over all elements in your collection anyway. But with the for loops in Java, you could do something like this: // Skips first two elements
for (int i = 2; i < list.size(); i++) {
// Do something here
} How are you going to achieve that with your funky functions, huh? Well, for that there's drop(): val numbers = (1..5).toList()
println(numbers.drop(2)) // [3, 4, 5] Do note that this doesn't modify the original collection in any way: println(numbers) // [1, 2, 3, 4, 5] If you would like to stop your loop earlier, there's dropLast() for that: println(numbers.dropLast(2)) // [1, 2, 3] Another interesting function is dropWhile(), in which it receives a predicate instead of a number. It skips until the predicate returns true for the first time: val readings = listOf(-7, -2, -1, -1, 0, 1, 3, 4)
println(readings.dropWhile {
it <= 0
}) // [1, 3, 4] And there's the accompanying dropLastWhile(). Sort family Don't worry, we won't have to implement our own sort algorithm. This is not CS 101. Having the list of people from the preceding find() example, we would like to sort them by age: val people = listOf(Person("Jane", "Doe", 19),
Person("John", "Doe", 24),
Person("John", "Smith", 23)) It is easily achieved with sortedBy(): println(people.sortedBy { it.age })
The preceding code prints the following output: [Person(firstName=Jane, lastName=Doe, age=19), Person(firstName=John, lastName=Smith, age=23), Person(firstName=John, lastName=Doe, age=24)] There's also sortedByDescending(), which will reverse the order of the results: println(people.sortedByDescending { it.lastName }) The preceding code prints the following output: [Person(firstName=John, lastName=Smith, age=23), Person(firstName=John, lastName=Doe, age=24), Person(firstName=Jane, lastName=Doe, age=19)] And if you want to compare by more than one parameter, use the combination of sortedWith and compareBy: println(people.sortedWith(compareBy({it.lastName}, {it.age}))) ForEach This is the first terminator we'll see. Terminator functions return something other than a new collection, so you can't chain the result of this call to other calls. In the case of forEach(), it returns Unit. So it's like the plain, old for loop:
val numbers = (0..5)
numbers.map { it * it} // Can continue
.filter { it < 20 } // Can continue
.sortedDescending() // Still can
.forEach { println(it) } // Cannot continue Do note that forEach() has some minor performance impacts compared to the traditional for loop. There's also forEachIndexed(), which provides an index in the collection alongside the actual value: numbers.map { it * it }
.forEachIndexed { index, value ->
print("$index:$value, ")
}
The output for the preceding code will be as follows: 0:1, 1:4, 2:9, 3:16, 4:25, Since Kotlin 1.1, there's also the onEach() function, which is a bit more useful, since it returns the collection again:
numbers.map { it * it}
.filter { it < 20 }
.sortedDescending()
.onEach { println(it) } // Can continue now
.filter { it > 5 }
Join family
In the previous example, we used the side effect of printing to the console, which is not favorable in terms of functional programming. What's more, we also have this ugly comma at the end of our output as follows: 0:1, 1:4, 2:9, 3:16, 4:25, There must be a better way. How many times have you had to actually write code to simply concatenate some list of values into a string? Well, Kotlin has a function for that: val numbers = (1..5)
println(numbers.joinToString { "$it"})
The preceding code will give the following output: 1, 2, 3, 4, 5
Simply beautiful, isn't it? And if you want to separate it with other characters, or don't want spaces, there's a way to configure it: println(numbers.joinToString(separator = "#") { "$it"}) The output of the preceding code will be as follows: 1#2#3#4#5 Fold/Reduce Much like forEach(), both fold() and reduce() are terminating functions. But instead of terminating with Unit, which is not useful, they terminate with a single value of the same type. The most common example of reduce is, of course, for adding up stuff. With the list of people from the previous example, we can do the following:
println(people.reduce {p1, p2 ->
Person("Combined", "Age", p1.age + p2.age)
})
The output of the preceding code will be as follows:
Person(firstName=Combined, lastName=Age, age=64)
Well, combining a lot of people into one doesn't make much sense, unless you're a fan of some horror movies. But with reduce, we can also compute who's the oldest or the youngest in the list:
println(people.reduce {p1, p2 ->
if (p1.age > p2.age) { p1 } else { p2 }
})
The second function we're about to discuss, fold(), is much like reduce, but it takes another argument, which is the initial value. It's useful when you've already computed something, and now want to use this intermediate result:
println(people.drop(1) // Skipping first one
.fold(people.first()) // Using first one as initial value
{p1, p2 ->
Person("Combined", "Age", p1.age + p2.age)
})
Code examples:
1.CollectionMutableExample.kt :
package functional.immutability
import java.util.*
import kotlin.concurrent.thread
fun main(args: Array<String>) {
val counter = ScoreCollector()
thread(isDaemon = true, name = "Maleficent") {
while (true) counter.scores.clear()
}
for (i in 1..1_000) {
counter.scores += Random().nextInt(100)
println(counter.scores.sumBy { it } / counter.scores.size)
}
}
data class ScoreCollector(val scores: MutableList<Int> = mutableListOf())
Output :
23
54
63
66
68
70
67
68
70
70
64
60
62
59
60
61
60
58
56
55
55
57
55
56
55
57
57
55
54
54
Exception in thread "main" java.lang.ArithmeticException: / by zero
at FileKt.main (File.kt:17)
at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0 (:-2)
at jdk.internal.reflect.NativeMethodAccessorImpl.invoke (:-1)
2.CollectionImmutableExample.kt :
package functional.immutability
import java.util.*
import kotlin.concurrent.thread
fun main(args: Array<String>) {
val counter = ImmutableScoreCollector(List(1_000) {
Random().nextInt(100)
})
thread(isDaemon = true, name = "Maleficent") {
//while(true) counter.scores.clear()
}
}
data class ImmutableScoreCollector(val scores: List<Int>)
Will continue in next blog....
No comments:
Post a Comment