Ich habe eine Scala-App mit einer Liste von Elementen mit Kontrollkästchen, so dass der Benutzer einige auswählt und auf eine Schaltfläche klickt, um sie um eine Position nach oben zu verschieben (links). Ich entschied mich, eine Funktion zu schreiben, um Elemente eines beliebigen Typs zu verschieben, die einem bestimmten Prädikat entsprechen. Also, wenn Sie diese Elemente haben:
%Vor%und das Prädikat ist "Großbuchstaben", die Funktion würde dies zurückgeben:
%Vor%Kurz gesagt, jede Folge zusammenhängender Elemente, die das Prädikat erfüllen, wird mit dem einzelnen Element links davon getauscht.
Ich habe die folgende hässliche imperative Implementierung gefunden. Ich würde gerne eine schöne und hoffentlich lesbare, funktionale Lösung sehen.
%Vor%EDIT: Danke allen, ich hoffe euch hat die Übung gefallen!
Hier ist eine rein funktionale Implementierung
%Vor%Und hier ist eine, die Mutabilität auf der Innenseite verwendet, um schneller zu sein
%Vor% Das könntest du wahrscheinlich über foldLeft (auch bekannt als /: ) tun:
Es muss mit der leeren Zeichenfolge gearbeitet werden, aber:
%Vor%Ich lasse es als eine Übung, wie dies in die Array-basierte Lösung
geändert werdenDies ist im Grunde ein imperativer Algorithmus mit einem funktionalen Stil.
%Vor%Ändert das Array an Ort und Stelle, mit einem Nebeneffekt. Ich denke, es ist wirklich wie die Version in der Frage, außer es ist einfacher zu lesen. Imperativ muss nicht hässlich sein ...
Bearbeiten: verdammt, konnte nicht einschlafen, bis ich dies niedergeschrieben habe (wie oben, nur kompakter):
%Vor%Ich beanspruche dieses Zeug nicht, um effizient oder lesbar zu sein. Leider scheinen all die guten Antworten zu sein, also bin ich auf Originalität bedacht. : -)
%Vor% Also, hier ist was passiert. Zuerst verknüpfe ich jedes Zeichen mit seinem Index ( a.zipWithIndex ) und dann getrennt in areP und notP abhängig davon, ob das Zeichen p erfüllt oder nicht.
An diesem Punkt habe ich zwei Sequenzen, die jeweils aus einem Zeichen und seinem Index in der ursprünglichen Sequenz bestehen.
Als nächstes verschiebe ich einfach den Index der Elemente in der ersten Sequenz, indem ich 1 subtrahiere und shifted berechne.
Die Berechnung des neuen Index der unverschobenen Elemente ist viel schwieriger. Für jedes dieser Elemente ( notP map ) mache ich ein foldLeft . Der Akkumulator der linken Falte ist das Element selbst (immer mit seinem Index). Die Sequenz, die gefaltet wird, ist die Folge von verschobenen Elementen - so kann man sehen, dass ich für jedes unverschobene Element die ganze Folge von verschobenen Elementen durchquere (sehr ineffizient!).
Also vergleichen wir den Index des unverschobenen Elements mit dem Index jedes verschobenen Elements. Wenn sie gleich sind, erhöhen Sie den Index des unverschobenen Elements. Da die Reihenfolge der verschobenen Elemente geordnet ist ( partition ändert die Reihenfolge nicht), wissen wir, dass wir zuerst nach niedrigeren Indizes und dann nach höheren Indizes testen werden, um sicherzustellen, dass ein Index seinen Index um so viel wie erhöht erhöht notwendig.
Damit verbinden wir die beiden Sequenzen, sortieren sie nach ihren neuen Indizes und ordnen sie dann dem Element zu.
Hier ist eine andere Variante von Geoffs Antwort:
%Vor%Schnell getestet mit
%Vor%Hier ist Version zwei
%Vor% Ich weiß nicht genug, um es in Scala zu schreiben, aber dieses Problem ist maßgeschneidert für die Listenfunktionen takeWhile und dropWhile . Die Idee ist, dass Sie die Liste der Elemente in drei Teile aufteilen:
Linker Teil, berechnet mit takeWhile , enthält Elemente ganz links, die das Prädikat nicht erfüllen.
Der mittlere Teil ist die Gruppe der Elemente, die Sie nach links verschieben möchten, berechnet durch Ablegen der linken Elemente und dann takeWhile den Rest.
Der rechte Teil ist alles übrig; dropWhile die mittleren Elemente.
Hier ist es in Haskell:
%Vor%Und hier ist ein Einzeltest:
%Vor% Haskell-Programmierer könnten List.break oder List.span verwenden, um Aufrufe von takeWhile und dropWhile zu kombinieren, aber ich bin mir nicht sicher, ob Scala diese Dinge hat. Außerdem sind takeWhile und dropWhile nette sinnvolle Namen, während ich zumindest break und span weniger klar finde.
BEARBEITEN : Fixierter rekursiver Aufruf, um shift p right anstelle von right aufzurufen, um alle Gruppen nach oben zu verschieben.
Bearbeiten: Dies löst das gestellte Problem nicht wirklich - es löst ein verwandtes, aber anderes Problem (Erhöhung der Priorität markierter Elemente um eins). Ich verlasse es hier jedoch als Referenz.
Hier ist ein "Einzeiler", der die gewünschten Arrays für Scala 2.8 verwendet.
%Vor%Ich überlasse es dem Leser als Übung, herauszufinden, wie es funktioniert. (Wenn Sie wirklich Generika mit T wollen, wird Ihnen in Scala 2.8 ein GenericArray zur Verfügung gestellt; Sie können das dann tun, wenn Sie ein primitives Java-Array wollen.)
Eine Lösung in J:
%Vor% Lasst uns das in benannte Stücke zum besseren Verständnis aufteilen. Die letzte Zeichenfolge " abDEcfgIh " ist das Ergebnis der Anwendung einer Funktion auf die Zeichenfolge " abcDEfghI ", die das richtige Argument für die Funktion ist. Das Alphabetepaar stellt das linke Argument der Funktion dar (das ist der Teil, der beginnt "( 4 : ..."). Also könnten wir anstelle des 2-Elemente-Vektors der Boxed Strings jede einzeln benennen:
Nun, da wir zwei Variablen " lc " und " uc " für die Klein- und Großbuchstaben haben, untersuchen wir den Hauptteil der Funktion im Detail. Nimmt man einen logisch kohärenten Block vom rechten Ende, da dies zuerst ausgewertet würde, könnten wir dies wie folgt benennen:
Dies definiert " rmUCshift " als etwas, das ein rechtes und linkes Argument benötigt (das " 4 : " gibt dies an), wobei der Körper in der nächsten Zeile beginnt und bis zum blos schließenden Paren fortfährt. Die Form " 4 : 0 ", gefolgt vom Körper, ist eine Variante der Form " 4 : 'body", die anfangs gezeigt wird. Dieses Verb rmUCshift kann unabhängig wie folgt aufgerufen werden:
Der Aufruf wird um drei Leerzeichen eingerückt und die Ausgabe folgt unmittelbar darauf. Das linke Argument (lc;'') ist ein Vektor mit zwei Elementen, wobei das leere Array als zweites Element angegeben ist, da es in diesem Teil des Codes nicht verwendet wird - wir hätten einen beliebigen Wert nach dem Semikolon verwenden können, aber die beiden einfachen Anführungszeichen sind leicht einzugeben .
Die nächsten zu benennenden Stücke sind diese (Definitionen gefolgt von Beispielen):
%Vor%Die Kombination dieser benannten Stücke ergibt folgendes:
%Vor% Die Wiederholung von " x rmUCshift y " ist jedoch unnötig und kann vereinfacht werden, um uns folgendes zu geben:
Tags und Links scala functional-programming