kotlin函數式編程_我最喜歡的Kotlin函數式編程示例

kotlin函數式編程

by Marcin Moskala

通過Marcin Moskala

One of the great things about Kotlin is that it supports functional programming. Let’s see and discuss some simple but expressive functions written in Kotlin.

Kotlin的一大優點是它支持函數式編程。讓我們看一下并討論一下用Kotlin編寫的一些簡單但富有表現力的函數。

收集處理 (Collection processing)

Kotlin has some of the best support for collection processing. It is expressive and supports a lot of functions. To see an example, let’s say that we make a system for a University. We need to find the best students that deserve a scholarship. We have following Student model:

Kotlin為收集處理提供了一些最好的支持。它具有表現力，并支持許多功能。來看一個例子，假設我們為大學建立了一個系統。我們需要找到值得獎學金的最好的學生。我們有以下Student模型：

class Student(val name: String,val surname: String,val passing: Boolean,val averageGrade: Double
)

Now we can make the following processing to get a list of the best 10 students that match all criteria:

現在，我們可以進行以下處理以獲取符合所有條件的10名最佳學生的列表：

students.filter { it.passing && it.averageGrade > 4.0 } // 1.sortedBy { it.averageGrade } // 2.take(10) // 3.sortedWith(compareBy({ it.surname }, { it.name })) // 4

We get only students who are passing and with a grade point average of greater than 4.0.
我們只會招收及格且平均分數高于4.0的學生。
We sort by the average grade.
我們按平均成績排序。
We take first 10 students.
我們招收了前10名學生。
We sort students alphanumerically. The comparator compares surnames first, and if equal then it compares names.
我們按字母數字排序學生。比較器首先比較姓氏，如果相等，則比較名字。

What if, instead of alphanumerical order, we need to keep students in the same order as they were before? What we can do is preserve the order using indexes:

如果我們需要讓學生保持以前的順序，而不是字母數字順序，該怎么辦？我們可以做的是使用索引保留順序：

students.filter { it.passing && it.averageGrade > 4.0 }.withIndex() // 1.sortedBy { (i, s) -> s.averageGrade } // 2.take(10).sortedBy { (i, s) -> i } // 3.map { (i, s) -> s } // 4

We add current index to every element.
我們將當前索引添加到每個元素。
We need to destructure value and index before use.
我們需要在使用前對值和索引進行解構。
We sort by index.
我們按索引排序。
We remove index and keep only students.
我們刪除索引，只保留學生。

This shows how simple and intuitive collection processing in Kotlin is.

這表明Kotlin中的收集過程非常簡單直觀。

電源組 (Powerset)

If you had algebra at your University, then you might remember what a powerset is. For any set, its powerset is the set of all its subsets including this set and the empty set. For instance, if we have the following set:

如果您在大學學習過代數，那么您可能會記得什么是冪集。對于任何集合，其冪集是其所有子集的集合，包括該集合和空集合。例如，如果我們有以下設置：

{1,2,3}

Its powerset is the following:

其功率集如下：

{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Such a function is very useful in algebra. How can we implement it?

這樣的函數在代數中非常有用。我們如何實施呢？

If you want to challenge yourself, then stop right now and try to solve it yourself first.

如果您想挑戰自己，請立即停止并嘗試自己解決問題。

Let’s start our analysis from simple observation. If we take any element of the set (like 1), then the powerset will include an equal number of sets with these elements ({1}, {1,2}, {1,3}, {1,2,3}), and without these ({}, {2}, {3}, {2,3}).

讓我們從簡單的觀察開始分析。如果我們采用集合的任何元素(如1)，則冪集將包含與這些元素相等的集合({1}, {1,2}, {1,3}, {1,2,3}) ，而沒有這些({}, {2}, {3}, {2,3}) 。

Note that the second is a powerset({2,3}), and the first is a powerset({2,3}) with 1 added to every set. So we can calculate the powerset by taking the first element, calculating the powerset for all others, and returning the sum of the result and the result with the first element added to every set:

請注意，第二個是powerset({2,3}) ，第一個是powerset({2,3}) ，每個集合中都添加了1。因此，我們可以通過采用第一個元素，計算所有其他元素的冪集，然后返回結果與將第一個元素添加到每個集合中的結果的和，來計算冪集：

fun <T> powerset(set: Set<T>): Set<Set<T>> {val first = set.first()val powersetOfRest = powerset(set.drop(1))return powersetOfRest.map { it + first } + powersetOfRest
}

The above declaration will not work correctly. The problem is with the empty set: first will throw an error when the set is empty. Here, the definition comes with a solution: powerset({}) = {{}}. When we fix it, we will have our algorithm ready:

上面的聲明將無法正常工作。問題出在空集合上：當??集合為空時， first將引發錯誤。在這里，定義附帶一個解決方案：powerset({})= {{}}。修復后，我們將準備好算法：

fun <T> powerset(set: Set<T>): Set<Set<T>> =if (set.isEmpty()) setOf(emptySet())else {val powersetOfRest = powerset(set.drop(1))powersetOfRest + powersetOfRest.map { it + set.first() }}

Let’s see how it works. Let’s say we need to calculate the powerset({1,2,3}). The algorithm will count it this way:

讓我們看看它是如何工作的。假設我們需要計算powerset({1,2,3}) 。該算法將以這種方式對其進行計數：

powerset({1,2,3}) = powerset({2,3}) + powerset({2,3}).map { it + 1 }

powerset({2,3}) = powerset({3}) + powerset({3}).map { it + 2}

powerset({3}) = powerset({}) + powerset({}).map { it + 3}

powerset({}) = {{}}

powerset({3}) = {{}, {3}}

powerset({2,3}) = {{}, {3}} + {{2}, {2, 3}} = {{}, {2}, {3}, {2, 3}}

powerset({1,2,3}) = {{}, {2}, {3}, {2, 3}} + {{1}, {1, 2}, {1, 3}, {1, 2, 3}} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

The above function can be improved. We can use the let function to make the notation shorter and more compact:

可以改善上述功能。我們可以使用let函數使符號更短，更緊湊：

fun <T> powerset(set: Set<T>): Set<Set<T>> =if (set.isEmpty()) setOf(emptySet())else powerset(set.drop(1)).let { it+ it.map { it + set.first() }

We can also define this function as an extension function to Collection so we can use this function as if it is the method of Set (setOf(1,2,3).powerset() instead of powerset(setOf(1,2,3))):

我們還可以將此函數定義為Collection的擴展函數，因此可以像使用Set ( setOf(1,2,3).powerset()而不是powerset(setOf(1,2,3)) )：

fun <T> Collection<T>.powerset(): Set<Set<T>> =if (isEmpty()) setOf(emptySet())else drop(1).powerset().let { it+ it.map { it + first() }

One big improvement is to make the powerset tail recursive. In the above implementation, the state of powerset is growing with every iteration (recurrent call), because the state of the previous iteration needs to be kept in the memory.

一項重大改進是使powerset尾遞歸。在上面的實現中， powerset的狀態隨著每次迭代(循環調用)而增長，因為前一個迭代的狀態需要保留在內存中。

Instead, we could use an imperative loop or the tailrec modifier. We will use the second option to maintain the readability of the function. The tailrec modifier allows only a single recursive call in the last statement. This is how we can change our function to use it effectively:

相反，我們可以使用命令式循環或tailrec修飾符。我們將使用第二個選項來保持功能的可讀性。 tailrec修飾符僅允許在最后一條語句中進行單個遞歸調用。這是我們可以更改功能以有效使用它的方法：

fun <T> Collection<T>.powerset(): Set<Set<T>> = powerset(this, setOf(emptySet()))private tailrec fun <T> powerset(left: Collection<T>, acc: Set<Set<T>>): Set<Set<T>> =if (left.isEmpty()) accelse powerset(left.drop(1), acc + acc.map { it + left.first() })

The above implementation is part of the KotlinDiscreteMathToolkit library, which defines a lot of other functions used in discrete math.

上面的實現是KotlinDiscreteMathToolkit庫的一部分，該庫定義了離散數學中使用的許多其他函數。

快速排序 (Quicksort)

Time for my favorite example. We’ll see how a difficult problem can be simplified and made highly readable using a functional programming style and tools.

現在是我最喜歡的例子。我們將看到如何使用功能性編程風格和工具簡化難題并使其具有更高的可讀性。

We will implement the Quicksort algorithm. The algorithm is simple: we choose some element (pivot) and we distribute all other elements to the list with bigger and smaller elements than the pivot. Then we recursively sort these sub-arrays. Finally, we add the sorted list of smaller elements, the pivot, and the sorted list of bigger elements. For simplification, we will take the first element as a pivot. Here is the full implementation:

我們將實現Quicksort算法。該算法很簡單：我們選擇一些元素(數據透視)，然后將所有其他元素分布到列表中，其中元素的大小大于數據透視。然后，我們對這些子數組進行遞歸排序。最后，我們添加較小元素的排序列表，數據透視表和較大元素的排序列表。為了簡化，我們將第一個元素作為樞軸。這是完整的實現：

fun <T : Comparable<T>> List<T>.quickSort(): List<T> = if(size < 2) thiselse {val pivot = first()val (smaller, greater) = drop(1).partition { it <= pivot}smaller.quickSort() + pivot + greater.quickSort()}
// Usage
listOf(2,5,1).quickSort() // [1,2,5]

Looks great, doesn’t it? This is the beauty of functional programming.

看起來不錯，不是嗎？這就是函數式編程的美。

The first concern of such a function is its execution time. It is not optimized for performance at all. Instead, it is short and highly readable.

這種功能首先要考慮的是它的執行時間。根本沒有針對性能進行優化。相反，它很簡短并且可讀性強。

If you need a highly optimized function, then you can use one from the Java standard library. It is based on different algorithms depending on some conditions, and it has actual implementations written naively. It should be much more efficient. But how much exactly? Let’s compare these two functions. Let’s sort a few different arrays with random elements and compare execution times. Here is the code I’ve used for this purpose:

如果需要高度優化的功能，則可以使用Java標準庫中的一種。它基于某些條件基于不同的算法，并且天真的編寫了實際的實現。它應該更加有效。但是多少呢？讓我們比較這兩個函數。讓我們用隨機元素對幾個不同的數組進行排序，并比較執行時間。這是我用于此目的的代碼：

val r = Random()
listOf(100_000, 1_000_000, 10_000_000).asSequence().map { (1..it).map { r.nextInt(1000000000) } }.forEach { list: List<Int> ->println("Java stdlib sorting of ${list.size} elements took ${measureTimeMillis { list.sorted() }}")println("quickSort sorting of ${list.size} elements took ${measureTimeMillis { list.quickSort() }}")}

On my machine I got the following result:

在我的機器上，我得到以下結果：

Java stdlib sorting of 100000 elements took 83quickSort sorting of 100000 elements took 163Java stdlib sorting of 1000000 elements took 558quickSort sorting of 1000000 elements took 859Java stdlib sorting of 10000000 elements took 6182quickSort sorting of 10000000 elements took 12133`

Java stdlib排序100000個元素花費83quickSort排序100000個元素花費163Java stdlib排序1000000個元素花費558quickSort排序1000000個元素花費859Java stdlib排序10000000個元素花費6181quickSort排序10000000個元素花費12133`

As we can see, the quickSort function is generally 2 times slower. Even for huge lists. It has the same scalability. In normal cases, the difference will generally be between 0.1ms vs 0.2ms. Note that it is much simpler and more readable. This explains why in some cases we can use a function that’s a bit less optimized, but readable and simple.

如我們所見， quickSort 功能通常要慢2倍。即使是巨大的清單。它具有相同的可伸縮性。在正常情況下，差異通常在0.1ms與0.2ms之間。請注意，它更加簡單易讀。這就解釋了為什么在某些情況下我們可以使用優化程度略低但可讀性和簡單性強的函數。

If you are interested in Kotlin, check out Kotlin Academy. It is great publication and community dedicated for Kotlin.

如果您對Kotlin感興趣，請訪問Kotlin Academy 。這是Kotlin的重要出版物和社區。

I am also publishing great resources on my Twitter. To mention me there use @marcinmoskala. If you can use my help, remember that I am open for consultations.

我還在Twitter上發布了大量資源。要在這里提及我，請使用@marcinmoskala 。如果可以使用我的幫助，請記住我愿意接受咨詢。