Listen in 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 knapp und elegant er ist, als dasselbe in einer imperativen 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 sich an einem voll funktionsfähigen Stil zu versuchen. Wir können alle komplexen Funktionen, die wir benötigen, aus den drei 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 sehr langsam ist und nicht in Produktionsanwendungen verwendet werden sollte. Es gibt sicherlich Möglichkeiten zur Verbesserung, aber der Zweck des Artikels besteht nicht darin, diese Möglichkeiten offenzulegen, sondern einen alternativen Ansatz zum Schreiben von Code in Betracht zu ziehen. In jedem Fall hilft Ihnen das Verständnis dieses Ansatzes bei rekursiven Datenstrukturen, und vielleicht werden Sie die Schönheit und Eleganz des Lesens des Codes zu schätzen wissen und wie viel einfacher es ist, ihn zu verstehen.

    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, werden die ersten zurückgegeben, andernfalls wird ein Fehler zurückgegeben.
    Wir haben nicht die Möglichkeit, einen solchen Code zu schreiben, aber im Allgemeinen, wenn Sie genau hinschauen, ist es sehr ähnlich wie bei der Vorlage. Wir werden auch die Erweiterungsfunktion verwenden, um diese Methode später auf Listen anwenden zu können und um den Wert etwas prägnanter zu erhalten, ohne die Klammern am Ende, wie bei einem Methodenaufruf.

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

    Um die Rekursion bequem zu nutzen, 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 Musterübereinstimmung, die Entwickler im selben Stil beschreiben können. Deshalb müssen wir hier ein wenig schreiben, wann.

    val  List.tail: List
       get() = drop(1)
    

    Es ist etwas unredlich, eine Funktion aus der Sprachbibliothek zu verwenden. Auf der anderen Seite müssten wir jedoch Code für diese Methode schreiben, sodass es besser wäre, bereits funktionierende Methoden zu verwenden.

    Jetzt können wir die Liste in das erste Element und den Rest der Liste unterteilen. Wir werden auch die Funktion der Verkettung der Liste und eines Elements benötigen, die später für die Konvertierung und andere Operationen in der Liste aktiv verwendet werden.

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

    Jetzt können wir dem Element am Ende eine Liste hinzufügen, und unsere Implementierung der Kartenfunktion wird funktionsfähig und 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 () . Schauen wir uns an, was wir gerade haben:

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

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

    val  List.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 wollen 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 = 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 in diesem Code nicht auf Ausführungsgeschwindigkeit und -optimierungen achten, können wir nicht umhin, uns an die Funktionen der Sprache für die Verwendung der Endrekursion zu erinnern. Die Schwanzrekursion ist ein spezieller Fall 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 es Ihnen garantiert ermöglicht, den Code für die Iteration neu zu erstellen. 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 mag den Anschein haben, dass die Funktion des von uns beschriebenen Betrags genau so ist, da der letzte Aufruf sum (xs.tail) ist . Dies ist jedoch nicht wahr. Wenn Sie den Code ein wenig anders beschreiben, wird es offensichtlich:

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

    Nun sehen wir, dass der letzte Aufruf die Summe des ersten Elements und des verbleibenden Teils des Schwanzes ist.

    Die gute Nachricht ist, dass die IDE Ihnen mitteilt, dass dies nicht der Fall ist, wenn Sie einer Funktion den Modifikator tailrec hinzufügen . Dies zu beheben ist jedoch ziemlich einfach. Ein häufiger Trick, mit dem eine Funktion festgelegt wird, ist die Verwendung einer Hilfsvariablen zum Speichern der Ergebnisse. Es sieht so aus:

    tailrec fun sum(xs: List, 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 2. Parameter zu übergeben. Um dies vollständig zu idiomatisieren, werden wir die Funktion ein bisschen mehr wiederholen und die Hauptberechnungen in der internen Funktion ausblenden, ohne dass die Außenwelt Zugriff auf den Parameter hat, auf den sie sich bezieht nicht benötigt.

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

    Mit diesem Wissen können wir sehen, dass die Größenfunktion, die wir oben implementiert haben, nicht die notwendigen Bedingungen für die Schwanzrekursion erfüllt.

    Jetzt können wir mit Kotlin Karten erstellen, filtern und reduzieren. Später werden wir sehen, dass es ausreichte, nur den letzten zu realisieren, und der Rest ist im Allgemeinen Ableitungen davon. Aber das Wichtigste zuerst.

    Hauptfunktionen


    KARTE


    Eine iterative Implementierung dieser Funktion setzt eine sequentielle Bewegung durch die Liste voraus, wobei die Konvertierungsfunktion verwendet wird und alle empfangenen Elemente der neuen Sammlung hinzugefügt werden. Wir werden rekursive Aufrufe verwenden, bei denen die Randbedingung eine leere Liste ist. Dann sieht die Implementierung so aus:

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

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

    Wir haben jedoch immer noch keine Funktion, um ein Element und eine Liste zu verketten. Aber wir können es schon realisieren. Zunächst leiten wir einen allgemeineren Fall ab, bei dem ein Listenpaar verkettet und dann verwendet wird, um dem Element eine weitere Liste hinzuzufügen.

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

    Filter


    Die Implementierung wird sehr ähnlich zu map 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, das wir erhalten haben, als Parameter auf. Die Implementierung sieht folgendermaßen aus:

    fun  List.filter(f: (T) -> Boolean): List = 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 nur mit dem Ende der Liste weiter.

    VERRINGERN


    Die am schwierigsten zu verstehende und gleichzeitig mächtigste Funktion (in der funktionalen Welt wird sie als Falte bezeichnet ). Am häufigsten wird es verwendet, um eine Liste auf ein einzelnes Element zu reduzieren. Sie haben einen Startwert s0 und es gibt auch eine Liste von Elementen a [] und eine Funktion f , die einen neuen Wert für den Startwert und das nächste Element der Liste zurückgibt. f (s0, a [0]) = s1 . Und so durchlaufen wir nacheinander die gesamte Liste der Elemente und erhalten am Ausgang einen einheitlichen Wert. Ein weit verbreitetes 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  reduce(s: T, xs: List, f: (T, R) -> T): T = when (xs.size) {
       0 -> s
       else -> reduce(f(s, xs.head), xs.tail, f)
    }
    

    Grundsätzlich entspricht die Implementierung genau der oben beschriebenen. 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 damit endet, stellen Sie sich vor, dass wir eine andere Liste als Startwert verwenden. 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 zum Beispiel, die Reduktionsfunktion so zu verwenden, dass die Ausgabe die ursprüngliche Liste ist:

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

    Nun, ich denke, Sie vermuten, dass wir für die alternative Implementierung von Map-Filtern Reduce verwenden könnten. Da wir gelernt haben, mit reduct 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  List.map2(f: (T) -> R): List = reduce(mutableListOf(), this) 
      { xs, s -> (xs + f(s)).toMutableList() }
    fun  List.filter2(f: (T) -> Boolean): List =  reduce(mutableListOf(), this)
      { ys, s ->
         if (f(s))
             return@reduce (ys + s).toMutableList()
         else
             ys
      }
    

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

    fun  reduceRight(s: T, xs: List, 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. Bei dieser Option können Sie auch Änderungen hinzufügen, bei denen das letzte Element der Liste als Startwert verwendet wird.

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

    Implementieren wir auch die zip- Funktion , mit der wir 2 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  zip(xs: List, ys: List): List> {
       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, wodurch Sie anstelle der Rückgabe eines Elementpaares eine bestimmte Funktion auf zwei Elemente anwenden können. In Haskell heißt diese Funktion zipWith . Und es ist mit der Funktionalität implementiert, die wir sehr einfach geschrieben haben:

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

    Sehr häufig treten bei der Verwendung des funktionalen Ansatzes Probleme auf, wenn Sie Manipulationen durchführen müssen, die nicht auf Objekten in Listen basieren, sondern auf Indizes. Zum Beispiel müssen wir alle geraden Elemente einer Liste summieren. Sie können versuchen, dies durch Reduzieren zu erreichen, indem Sie Pair als aktuellen Wert beibehaltenund Hinzufügen eines Wertes, wenn flag == true, und jedes Mal für den nächsten Schritt die Negation von flag. 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, genügt es, zip für die Liste und Sequenz aufzurufen [0,1,2 ..]

    fun sumWithEvenIndexes(xs: List) =
           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 zum Schreiben dieses Handbuchs inspiriert hat, und wie die Implementierung in einer imperativen Sprache in Kotlin und ganz am Ende in Haskell aussieht.

    Es ist notwendig, den Maximalbetrag zwischen 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 Hinzufügen von Elementen keine Gedanken über ein Überlaufen machen.

    Imperativer Java-Ansatz:

    public Integer maxSum(List 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 selbst als Workout zu implementieren):

    fun maxSum(xs: List) = 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 in Kotlin implementiert haben (wir könnten übrigens Reduce verwenden, um dieses Problem zu lösen), dem, was in Haskell geschrieben werden kann, sehr ähnlich.

    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 ist fast alles, was geschrieben wurde, in der Kotlin-Standardbibliothek enthalten. In Zukunft werden Sie also möglicherweise den von Kotlin bereitgestellten Funktionsstil verwenden, anstatt eine weitere for-Schleife zu schreiben.

    Das Schwierigste im funktionalen Stil ist wahrscheinlich, dass das Problem auf verschiedene Arten gelöst werden kann. Das offensichtlichste kann in Zukunft umständlich und schwer zu verstehen sein, und das verständlichste zu schreiben kann Zeit und ernstes Nachdenken erfordern. Das Einzige, was beim Meistern helfen kann, ist ständiges Üben und Trainieren.

    PS: Wie oben angegeben, können Sie das Repository anzeigenmit allen Beispielen, die in dem Artikel sind. 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 später https://arrow-kt.io/ . Meiner Meinung nach sollten Sie es sich nicht gleich ansehen, da alles ziemlich beängstigend aussieht. Wenn Sie später von Funktoren und Monaden nicht erschreckt werden, sollten Sie es sich unbedingt ansehen.

    Jetzt auch beliebt: