Listen bei Kotlin. Haskell Ansatz

Haskell ist eine voll funktionsfähige und äußerst prägnante Sprache. Jeder, der jemals versucht hat, Code in Haskell zu schreiben, merkt, wie prägnant und elegant es ist, als dasselbe in einer zwingenden Sprache zu schreiben. Dasselbe in Java zu erreichen, ist meiner Meinung nach unmöglich, aber Kotlin ermöglicht es Ihnen, sich in diese Richtung zu bewegen und einen voll funktionsfähigen Stil auszuprobieren. Wir können alle komplexen Funktionen, die wir benötigen, von der Startbasis der 3 bekanntesten Funktionen ableiten: Map, Filter, Reduce. Außerdem habe ich ein Repository erstellt , in dem Sie die Tests studieren und anzeigen können.

Bevor ich anfange, möchte ich darauf hinweisen, dass es sich nicht lohnt, einen funktionalen Ansatz auf diese Weise zu implementieren, da der Code kritisch langsam ist und nicht in Produktionsanwendungen verwendet werden sollte. Es gibt sicherlich Optionen zur Verbesserung, aber der Zweck des Artikels besteht nicht darin, diese Optionen offenzulegen, sondern einen alternativen Ansatz zum Schreiben von Code in Betracht zu ziehen. In jedem Fall hilft Ihnen ein Verständnis dieses Ansatzes bei rekursiven Datenstrukturen, und Sie werden möglicherweise die Schönheit und Eleganz des Lesens des Codes und dessen Verständnis schätzen.

Grundfunktionen

Listen spielen eine sehr wichtige Rolle in der Sprache, und viele nützliche Funktionen sind für sie implementiert. Schauen wir uns einige davon an und wie sie auf Kotlin implementiert werden können.

head (x:_) = x head [] = badHead 

Wenn die Liste Elemente enthält, geben wir das erste zurück, andernfalls geben wir einen Fehler zurück.
Wir haben nicht die Möglichkeit, einen solchen Code zu schreiben, aber wenn Sie genau hinschauen, ist er im Allgemeinen dem der Vorlage sehr ähnlich. Wir verwenden auch die Erweiterungsfunktion, um diese Methode später für Listen verwenden zu können und eine etwas präzisere Methode zu haben, um den Wert ohne die Klammern am Ende zu erhalten, wie bei einem Methodenaufruf.

 val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] } 

Um die Rekursion bequem nutzen zu können, möchten wir die Liste auch in das erste Element + alle anderen aufteilen. Versuchen wir, die Tail-Funktion dafür zu implementieren.

So sieht es auf haskell aus:

 tail (_:xs) = xs tail [] = errorEmptyList "tail" 

Leider bietet Kotlin keine solche Musterübereinstimmung, die Entwickler im gleichen Stil beschreiben können. Deshalb müssen wir hier ein wenig schreiben, wann.

 val <T> List<T>.tail: List<T> get() = drop(1) 

Es ist etwas unehrlich, eine Funktion aus der Sprachbibliothek zu verwenden, aber andererseits müssten wir auf jeden Fall Code für diese Methode schreiben, daher wäre es besser, Methoden zu verwenden, die bereits gut funktionieren.

Jetzt können wir die Liste in das erste Element + den Rest der Liste unterteilen. Wir benötigen außerdem die Funktion, die Liste und ein Element zu verketten, die später aktiv für die Konvertierung und andere Operationen in der Liste verwendet werden.

 operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) } 

Jetzt können wir dem Element am Ende eine Liste hinzufügen, und unsere Implementierung der Kartenfunktion funktioniert und ist einsatzbereit. Leider gibt es auch hier keine bequemere Möglichkeit, ein Objekt zur Liste hinzuzufügen . Daher verwenden wir die Methode add .

Im Moment haben wir fast alles was wir brauchen. Jetzt müssen wir nur noch die Randbedingung für das Verlassen der Rekursion beschreiben können. Dazu verwenden wir die Standardmethode isEmpty () . Lassen Sie uns anhalten und sehen, was wir im Moment haben:

• isEmpty () - Gibt es Elemente in der Liste?
• head - das erste Element der Liste
• Schwanz - eine Liste ohne das erste Element
• list + element - wir können die Liste mit einem Objekt verketten

Das ist alles, was wir brauchen, um alle Methoden zu bekommen, die wir brauchen.
Für meinen Geschmack wäre es bequemer, den Listenlängenvergleich in when- Anweisungen zu verwenden. Kotlin gibt uns bereits die Größe , um diese Listenlänge zu erhalten. Angenommen, wir möchten es selbst implementieren. Mit unserer Funktionalität wird es ganz einfach:

 val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size } 

Anwendung von Grundfunktionen

Betrachten Sie das häufigste Beispiel. Angenommen, wir haben eine Liste von ganzen Zahlen, und wir möchten sie zusammenfassen und dabei die Existenz von Zyklen vergessen. Alles, was wir haben, sind die Methoden, die wir oben abgeleitet haben, und die Rekursion. Dazu verwenden wir den gleichen Ansatz wie bei der Berechnung der Listengröße:

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) } 

Die Idee ist sehr einfach: Wenn die Liste keine Elemente enthält, ist die Summe 0; Andernfalls ist es die Summe des ersten Elements und ein rekursiver Aufruf der Summe für den Schwanz.

Trotz der Tatsache, dass wir uns nicht um Geschwindigkeit und Optimierungen in diesem Code kümmern, können wir nicht anders, als uns an die Fähigkeiten der Sprache zur Verwendung der Schwanzrekursion zu erinnern. Die Schwanzrekursion ist ein Sonderfall der Rekursion, bei dem ein rekursiver Aufruf die letzte Operation vor der Rückkehr von einer Funktion ist. Diese Art der Rekursion ist bemerkenswert, da Sie garantiert den Code für die Iteration neu erstellen können. Wie Sie wissen, besteht das Hauptproblem der Rekursion darin, dass während der Ausführung der Funktion der Aufrufstapel gespeichert werden muss, damit Sie bei Erreichen der Randbedingung zurückgehen und das Endergebnis neu berechnen können.

Es scheint, dass die Funktion des von uns beschriebenen Betrags einfach so ist, da der letzte Aufruf sum (xs.tail) ist . Dies ist jedoch nicht wahr. Wenn Sie den Code etwas anders beschreiben, wird klar:

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } } 

Jetzt sehen wir, dass der letzte Aufruf tatsächlich die Summe des ersten Elements und des verbleibenden Teils des Schwanzes ist.

Die gute Nachricht ist, dass die IDE Ihnen mitteilt , dass die Funktion dies nicht ist, wenn Sie einer Funktion den Modifikator tailrec hinzufügen. Dies zu beheben ist jedoch ziemlich einfach. Ein häufiger Trick, der eine Funktion korrigiert, besteht darin, eine Hilfsvariable zum Speichern der Ergebnisse zu verwenden. Es sieht so aus:

 tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) } 

Um die Summe der Elemente zu berechnen, reicht es aus, 0 als zweiten Parameter zu übergeben, und um sie vollständig idiomatisch zu machen, werden wir die Funktion ein wenig wiederholen und die Hauptberechnungen in der internen Funktion verbergen, ohne dass die Außenwelt Zugriff auf den Parameter hat, den sie enthält nicht benötigt.

 fun sum(xs: List<Int>):Int { tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sumInner(xs.tail, xs.head + acum) } return sumInner(xs, 0) } 

Mit diesem Wissen können Sie feststellen, dass die oben implementierte Größenfunktion nicht die erforderlichen Bedingungen für die Schwanzrekursion erfüllt.

Jetzt können wir Map, Filter und Reduce mit Kotlin implementieren. Später werden wir sehen, dass es ausreichte, nur letzteres zu realisieren, und der Rest sind im Allgemeinen Ableitungen davon. Aber das Wichtigste zuerst.

Hauptfunktionen

KARTE

Eine iterative Implementierung dieser Funktion umfasst das sequentielle Verschieben durch die Liste unter Verwendung der Konvertierungsfunktion und das Hinzufügen aller empfangenen Elemente zur neuen Sammlung. Wir werden rekursive Aufrufe verwenden, bei denen die Randbedingung eine leere Liste ist. Dann sieht die Implementierung folgendermaßen aus:

 fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) } 

Wenn die ursprüngliche Liste keine Elemente enthält, geben wir eine leere Liste zurück. Andernfalls wenden wir die Transformation auf das erste Element an und fügen am Ende einen rekursiven Aufruf für den Rest der Liste hinzu.

Wir haben jedoch immer noch keine Funktion zum Verketten eines Elements und einer Liste. Aber wir können es schon realisieren. Zunächst leiten wir einen allgemeineren Fall der Verkettung eines Listenpaars ab und verwenden ihn anschließend, um dem Element eine weitere Liste hinzuzufügen.

 operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) { 0 -> ArrayList(this) else -> (this + xs.head) + xs.tail } operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs 

Filter

Die Implementierung wird der Karte sehr ähnlich sein. Der einzige Unterschied besteht darin, dass Sie verstehen müssen, ob Sie das aktuelle Element zum Ergebnis hinzufügen müssen. Dazu rufen wir das Lambda auf, das wir als Parameter erhalten haben. Die Implementierung sieht folgendermaßen aus:

 fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) { 0 -> listOf() else -> if (f(head)) head + tail.filter(f) else tail.filter(f) } 

Wenn das aktuelle Element die Filterbedingung erfüllt, fügen Sie es rekursiv zum Ende der Liste hinzu. Andernfalls arbeiten wir weiterhin nur mit dem Ende der Liste.

REDUZIEREN

Die am schwierigsten zu verstehende und gleichzeitig leistungsstärkste Funktion (in der Funktionswelt wird sie als Fold bezeichnet ). Meistens wird es verwendet, um eine Liste auf ein einzelnes Element zu reduzieren. Sie haben einen bestimmten Startwert s0 und es gibt auch eine Liste der Elemente a [] und eine Funktion f , die einen neuen für den Startwert und das nächste Element der Liste zurückgibt. f (s0, a [0]) = s1 . Und so gehen wir nacheinander die gesamte Liste der Elemente durch und erhalten eine Art Einzelwert am Ausgang. Ein ziemlich häufiges Beispiel ist die Summierung von Array-Elementen. In diesem Fall ist der Startwert 0 und die Funktion gibt die Summe zweier Elemente zurück: f (s, a [i]) = s + a [i] . Überlegen Sie, wie wir diese Funktion rekursiv implementieren können.

 fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> reduce(f(s, xs.head), xs.tail, f) } 

Im Prinzip ist die Implementierung genau die gleiche wie oben beschrieben. Wenn die Liste keine Elemente enthält, geben wir den aktuellen Wert zurück. Andernfalls berechnen wir das neue erste Element und rufen erneut die Reduktionsfunktion für dieses Element und das Ende der Liste auf.

Beachten Sie, dass wir auch Änderungen an dieser Funktion vornehmen können. Übergeben Sie beispielsweise nicht den Startwert, sondern verwenden Sie dazu das erste Element der Liste. Um zu verstehen, dass Reduzieren nicht dort endet, stellen Sie sich vor, wir verwenden eine andere Liste als Startwert. In diesem Fall speichern wir jedes Mal bei der Iteration nicht einen Wert, sondern eine Liste, dank derer unsere Fähigkeiten erheblich zunehmen. Versuchen wir beispielsweise, die Reduzierungsfunktion so anzuwenden, dass die ursprüngliche Liste am Ausgang angezeigt wird:

 fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s } 

Nun, ich denke, Sie vermuten, dass wir für eine alternative Implementierung der Karte den Filter reduzieren könnten. Da wir gelernt haben, mit reduzieren genau dieselbe Liste zurückzugeben, müssen wir nur sehr wenige Änderungen vornehmen, um jedes Element konvertieren zu können. Für Filter ist alles sehr ähnlich.

 fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) { xs, s -> (xs + f(s)).toMutableList() } fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> = reduce(mutableListOf(), this) { ys, s -> if (f(s)) return@reduce (ys + s).toMutableList() else ys } 

Außerdem vergessen sie oft, dass wir Reduce auch nicht vom Anfang der Liste, sondern vom Ende verwenden können. Natürlich können wir die Liste einfach erweitern und danach reduzieren, aber das ist nicht interessant. Versuchen wir zu schreiben und zu verstehen, wie Reduzieren funktioniert, um die Liste in umgekehrter Reihenfolge zu reduzieren.

 fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> f(reduceRight(s, xs.tail, f), xs.head) } 

Wenn die Liste nicht leer ist, wenden wir die Funktion f auf das Ergebnis des Faltens des Endes der Liste und des Kopfes der Liste an. Somit wird das erste Element zuletzt verarbeitet; vorletzte - 2. und so weiter. Für diese Option können Sie auch Änderungen hinzufügen, die das letzte Element der Liste als Startwert usw. verwenden.

Wenn Sie mit Listen arbeiten, können Sie fast immer eine Kombination dieser drei Funktionen verwenden, um das gewünschte Ergebnis zu erzielen.

Implementieren wir auch die Zip- Funktion, mit der wir zwei Listen kombinieren können.
Am Eingang bekommen wir 2 Listen. Und wir möchten eine Liste von Paaren zurückgeben, deren Länge dem Minimum der ursprünglichen Listen entspricht.

Wie üblich müssen Sie darüber nachdenken, die Rekursion zu beenden und eine Funktion zu schreiben.

 fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> { return when (xs.isEmpty() || ys.isEmpty()) { true -> listOf() false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail) } } 

Sie können Ihre eigenen Änderungen hinzufügen, sodass Sie, anstatt ein Elementpaar zurückzugeben, eine bestimmte Funktion auf zwei Elemente anwenden können. In Haskell heißt diese Funktion zipWith . Und es wird mit der Funktionalität implementiert, die wir sehr einfach schreiben konnten:

 fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> = zip(xs, ys).map { f(it.first, it.second) } 

Sehr oft treten bei Verwendung des funktionalen Ansatzes Probleme auf, wenn Sie Manipulationen durchführen müssen, die nicht auf Objekten in Listen, sondern auf Indizes basieren. Zum Beispiel müssen wir alle geraden Elemente einer Liste summieren. Sie können versuchen, dies zu erreichen, indem Sie Pair <Int, Boolean> als aktuellen Wert beibehalten und einen Wert hinzufügen, wenn flag == true, und die Flag-Negation jedes Mal für den nächsten Schritt übernehmen. Dies sieht jedoch nicht besonders hübsch aus, und der Leser muss herausfinden, was Sie mit diesem Code ausdrücken möchten. Kotlin hat unendlich viele Sequenzen und sie eignen sich hervorragend zur Lösung dieses Problems. Wenn wir analysieren, was wir tun möchten, stellt sich heraus, dass wir alle Elemente mit ungeraden Indizes herausfiltern und die verbleibenden summieren möchten. Und um Indizes erhalten zu können, reicht es aus, zip für die Liste und Sequenz [0,1,2 ..] aufzurufen.

 fun sumWithEvenIndexes(xs: List<Int>) = zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList()) .filter { it.second % 2 == 0 } .map { it.first } .sum() 

In der Kotlin-Standardbibliothek finden Sie die Zip-Funktion für das Sequenzpaar.

Schauen wir uns nun eine einfache Aufgabe an, die mich dazu inspiriert hat, diesen Leitfaden zu schreiben, und wie seine Implementierung in einer zwingenden Sprache in Kotlin und ganz am Ende in Haskell aussieht.

Es ist notwendig, den maximalen Betrag unter Paaren benachbarter Zahlen in einem Array von ganzen Zahlen zu berechnen. Die Länge des Arrays ist größer als 1, und Sie müssen sich beim Summieren von Elementen keine Gedanken über ein Überlaufen machen.

Imperativer Java-Ansatz:

 public Integer maxSum(List<Integer> array) { Integer max = array.get(0) + array.get(1); for (int i = 2; i < array.size(); i++) if (array.get(i) + array.get(i-1) > max) max = array.get(i) + array.get(i-1); return max; } 

Ein funktionaler Ansatz für Kotlin unter Verwendung schriftlicher Funktionen (ich schlage vor, die Max-Funktion als Training selbst zu implementieren):

 fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max() 

Haskell-Implementierung:

 maxSum xs = maximum $ zipWith (+) xs (tail xs) 

Wie wir sehen können, ist das, was wir auf Kotlin implementiert haben (wir könnten übrigens Reduce verwenden, um dieses Problem zu lösen), dem sehr ähnlich, was in Haskell geschrieben werden kann.

Fazit

Zweifellos sollte dies nicht in der Entwicklung verwendet werden, da alles nicht optimal implementiert wurde, nur um einen funktionalen Ansatz zu demonstrieren. Außerdem befindet sich fast alles, was geschrieben wurde, in der Kotlin-Standardbibliothek. Vielleicht verwenden Sie in Zukunft den funktionalen Stil, den Kotlin uns bietet, anstatt eine weitere for-Schleife zu schreiben.

Das wahrscheinlich Schwierigste im funktionalen Stil ist, dass das Problem auf verschiedene Arten gelöst werden kann. Das offensichtlichste kann in Zukunft umständlich und schwer zu verstehen sein, und das Schreiben des verständlichsten kann Zeit und ernsthafte Überlegungen erfordern. Das einzige, was beim Mastering helfen kann, ist ständiges Üben und Trainieren.

PS: Wie oben erwähnt, können Sie das Repository mit allen Beispielen im Artikel sehen. Führen Sie die Tests durch und sehen Sie, wie es funktioniert!

PPS: Sie können sich auch einen alternativen Ansatz ansehen, der ähnliche Funktionen implementiert.

Und sehen Sie sich später https://arrow-kt.io/ an . Meiner Meinung nach sollten Sie nicht sofort dorthin schauen, da alles ziemlich beängstigend aussieht, aber später, wenn Funktoren und Monaden Sie nicht erschrecken, sollten Sie es unbedingt studieren.