Echte funktionale Programmierung in Scala - Vergleich von Java, Clojure und Scala

Ich habe vor kurzem mit der Lektüre von Stuart Halloways Buch 'Programming in Clojure' begonnen. Ich glaube nicht, dass ich in naher Zukunft viele Unternehmensanwendungen in dieser Sprache schreiben werde, aber es schadet nie, den Horizont zu erweitern, und es ist eine sehr gute Lektüre. In seinem Buch demonstriert er einige der Vorteile der funktionalen Programmierung anhand eines Beispiels aus der Apache Commons Bibliothek: StringUtils.indexOfAny. Er hat auch einen Blog darüber geschrieben. In diesem Blogbeitrag vergleichen wir die Originalfunktion in Java, die Clojure-Version und eine Scala-Implementierung.

Für den Anfang: Hier ist die ursprüngliche Implementierung in Java:

[java]
// From Apache Commons Lang, https://commons.apache.org/lang/
public static int indexOfAny(String str, char[] searchChars) {
if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) {
return -1;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
for (int j = 0; j < searchChars.length; j++) {
if (searchChars[j] == ch) {
return i;
}
}
}
return -1;
}
[/java]

Beispielhafte Ergebnisse dieser Funktion sind:

[java]
StringUtils.indexOfAny(null, *) = -1
StringUtils.indexOfAny("" , *) = -1
StringUtils.indexOfAny(*, null) = -1
StringUtils.indexOfAny(*, []) = -1
StringUtils.indexOfAny("zzabyycdxx" ,['z' ,'a' ]) = 0
StringUtils.indexOfAny("zzabyycdxx" ,['b' ,'y' ]) = 3
StringUtils.indexOfAny("aba" , ['z' ]) = -1
[/java]

Und nun der Clojure-Code. Ich habe die Version aus dem Buch übernommen ( hier kostenlos zum Download). In der Buchversion sind drei Funktionen definiert, im Gegensatz zu der Version, die im Blogbeitrag gezeigt wird.

(defn indexed [s] (map vector (iterate inc 0) s))
(defn index-filter [pred coll]
  (wenn pred
  (for [[idx elt] (indiziert coll) :when (pred elt)] idx)))
(defn index-of-any [pred coll]
  (first (index-filter pred coll)))

Die drei definierten Funktionen sind:

1. indexed gibt eine Folge von Paaren zurück, wobei das erste Element der Index und die Folge das Element ist.
2. index-filter gibt eine Folge der Indizes der übereinstimmenden Prädikate in der Sammlung zurück. Der Funktionsaufruf (index-filter #{a b} "abcdbbb") ergibt zum Beispiel (0 1 4 5 6)
3. index-of-any ist die StringUtils-Funktion. Dies ist jetzt eine einfache Funktion, die nur das erste Ergebnis der Index-Filter-Funktion zurückgibt.

Wie Stuart in seinem Buch erwähnt hat, ist die Clojure-Version kürzer, weniger komplex und auch allgemeiner als die Java-Version. Es gibt keine Sonderfallbehandlung, wie z.B. die Prüfung auf Null oder leere Suchzeichen. Das alles funktioniert ganz natürlich in der funktionalen Version. Sie kann auch leicht für andere Funktionen als nur indexOfAnyerweitert werden. Da ich in letzter Zeit alle möglichen netten, aber nutzlosen kleinen Funktionen in Scala implementiert habe, dachte ich, es wäre eine gute Idee, ein nützlicheres Beispiel auszuprobieren. Schauen wir also mal, wie gut wir das mit Scala in ähnlicher Weise wie die Clojure-Version umsetzen können. Fast sofort stoßen wir auf das gefürchtete Null-Problem. Scala ist keine rein funktionale Sprache und Sie müssen darauf achten, dass Parameter, die weitergegeben werden, null sein können. Sie könnten natürlich die Eingabeargumente als Optionen angeben, aber dann muss der Aufrufer der Funktion immer noch entweder den Some- oder den None-Wert konstruieren, und dazu müsste der Aufrufer prüfen, ob er null ist oder nicht.Nachdem ich also einige Zeit über dieses Problem gemeckert hatte, beschloss ich, mich geschlagen zu geben und die Null-Prüfung durchzuführen. 1-0 für Clojure. Hier sind die drei in Scala implementierten Funktionen (Hinweis: Ich habe hier den Stamm verwendet, falls Sie das selbst ausprobieren möchten. Ich habe nicht getestet, ob das auch mit Version 2.7.5 funktioniert):

[scala]
def indexed(coll:Seq[Any]):Seq[Pair[Int,Any]] = {
if (coll==null) List()
(0 until coll.length).zip(coll)
//below an alternative, but here we have to traverse the list another time to reverse the elements...
//coll.zipWithIndex.map(p => p.swap)
}
def indexedFilter(pred:Seq[Any], coll:Seq[Any]):Seq[Int] = {
if (pred==null)List()
val idxList = indexed(coll)
for (p <- pred; idxPair <- idxList; if (p == idxPair._2)) yield (idxPair._1)
}
def indexOfAny(pred:Seq[Any], coll:Seq[Any]):Option[Int] = {
val res=indexedFilter(pred, coll)
if (res.isEmpty) None
else Some(res.first)
}
[/scala]

Der Definition der indizierten Funktion zu folgen, ist ein Kinderspiel: Scalas zip-Funktion für die Klasse List erledigt hier die Aufgabe. Es gibt auch die Funktion zipWithIndex, die fast das tut, was wir wollen. Sie gibt eine Liste von Tupeln zurück, aber in umgekehrter Reihenfolge wie das Clojure-Beispiel: Element zuerst, Index später.

Der indexedFilter verwendet genau wie das Clojure-Beispiel eine for-Verarbeitung (das for von Clojure ist keine traditionelle Schleife, sondern eine Sequenzverarbeitung). Für jedes Element in unserer Prädikatsfolge wird geprüft, ob es in den indizierten Tupeln vorhanden ist, die das Ergebnis der indizierten Funktion sind. Wenn ja, wird es der resultierenden Liste mit yield hinzugefügt. indexOfAny wird dann zu einer trivialen Funktion, die lediglich prüft, ob die resultierende Sequenz leer ist oder nicht. Anstatt -1 zurückzugeben, wenn nichts gefunden wird, habe ich in diesem Fall die Scala-Klasse Option verwendet, um das Ergebnis ausdrucksstärker zu machen. Die Funktion funktioniert zumindest wie erwartet:

scala> indexOfAny("ab", "cdef")
res3: Option[Int] = None
scala> indexOfAny("ab", "bcdefbbb")
res3: Option[Int] = None
scala> indexOfAny("fb", "bcdefbbb")
res4: Option[Int] = Some(4)

Fazit Alles in allem ist die Scala-Version gar nicht so schlecht. Der größte Nachteil gegenüber der Clojure-Version sind die beiden Null-Prüfungen, die wir durchführen müssen, und außerdem müssen wir in der indexOfAny-Funktion prüfen, ob die resultierende Liste leer ist oder nicht. In dieser Hinsicht gewinnt Clojure. Allerdings ist die Scala-Version immer noch ziemlich ordentlich und generisch und verbessert (zumindest meiner Meinung nach) die ursprüngliche Java-Version.

Update: Umgang mit unendlichen Sammlungen Stuart stellte in seinem Kommentar die Frage, wie die Scala-Version mit unendlichen Sammlungen umgehen würde. Die oben vorgestellte Version geht damit nicht sehr gut um. Sie erhalten z.B. einen OEM, wenn Sie versuchen, Stream.from(0) (das eine träge unendliche Liste aller natürlichen Zahlen konstruiert) an die indexed-Funktion zu übergeben. Außerdem wertet die indexedFilter-Funktion die gesamte Sammlung aus, was für die indexOfAny-Funktion absolut nicht notwendig ist. Um mit einer unendlichen Sammlung umzugehen, müssen wir die Funktionen etwas modifizieren und optimieren, so dass sie eher den Funktionen ähneln, die Stuart in seinem Blogbeitrag verwendet hat, als den Buchversionen. Die im Blogbeitrag verwendeten Clojure-Funktionen sehen wie folgt aus:

(defn indexed [s] (map vector (iterate inc 0) s))
(defn index-of-any [s chars]
  (some (fn [[idx char]] (if (get chars char) idx))
  (indiziert s)))

Die Scala-Version, die ich mir ausgedacht habe, lautet wie folgt:

[scala]
def lazyIndexed(coll:Seq[Any]):Seq[Pair[Int,Any]] = {
if (coll==null) Stream.empty
Stream.from(0).zip(coll)
}
def lazyIndexOfAny(pred:Seq[Any], coll:Seq[Any]):Option[Int] = {
if (pred==null) None
lazyIndexed(coll).dropWhile(ip => !pred.exists(p => (p == ip._2))).headOption.map(ip => ip._1)
}
[/scala]

Wie bereits erwähnt, implementiert Stream in Scala eine träge Liste, bei der die Elemente nur bei Bedarf ausgewertet werden. In diesem Fall lassen wir die Elemente aus der Liste fallen, die nicht in der Prädikatsfolge vorkommen. Der Kopf der verbleibenden Liste ist das erste übereinstimmende Ergebnis. Der offensichtliche Nachteil ist, dass dies zwar bei unendlichen Sammlungen funktioniert, aber nur, wenn eine Übereinstimmung gefunden werden kann, sonst haben wir immer noch Probleme.