In Java programmieren, in Scala denken


Als ich in einem Java-Forum ein kleines Progrämmchen als Antwort auf eine Frage geschrieben hatte, fiel mir auf, wie „ungewöhnlich“ meine Lösung war: Sie sah aus wie Scala, und vor ein paar Monaten hätte ich soetwas nicht geschrieben. Ob die Lösung nun besonders „gut“ ist, ist eine andere Frage – es ging ja nur darum, dem Fragesteller einen Schubs in die richtige Richtung zu geben. Trotzdem finde ich es bemerkenswert, wie Scala auch mein Denken in Java beeinflusst.

Die Aufgabe war, einen Haufen Münzen verschiedener Werte gerecht auf zwei Personen aufzuteilen, soweit das möglich ist. Ich fing mit der Implementierung einer rekursiven Lösung an, wobei ich die Ausgangsmenge und die Geldsäcke der beiden Personen wie üblich als java.util.List definierte. Das Problem war nun, dass ich alle Lösungen finden wollte und bei meinem Ansatz die veränderlichen Java-Listen bei der Rekursion immer wieder kopiert werden mussten, damit sich die verschiedenen Lösungswege nicht in die Quere kommen würden. An dieser Stelle hätte ich früher mit den Schultern gezuckt und eben einfach kopiert, aber jetzt störte mich das ganze so sehr, dass ich tatsächlich eine Mini-Implementierung von unveränderlichen Stacks als innere Klassen mitlieferte:

import java.util.NoSuchElementException;
public class Coins {
    
    private abstract static class Stack {
        abstract boolean isEmpty();
        abstract Stack pop();
        abstract int top();
        public Stack push(int n) { return new StackImpl(n, this); }
    }
    
    private static class Empty extends Stack {
        public boolean isEmpty() { return true; }
        public Stack pop() { throw new NoSuchElementException(); }
        public int top() { throw new NoSuchElementException(); }
        @Override  public String toString() { return ""; }
    }
 
    private static class StackImpl extends Stack {
        private final int n;
        private final Stack s;
        public StackImpl(int n, Stack s) { this.n=n; this.s=s; }
        public boolean isEmpty() { return false; }
        public Stack pop() { return s; }
        public int top() { return n; }
        @Override
        public String toString() { return s.toString() + " " + n; }
    }
...
}

Ja, das ist eine ziemlich krude Implementierung, aber sie funktioniert. Normalerweise würde ich das etwas ordentlicher schreiben (als separate Klassen mit Generics), oder noch besser, mir eine Bibliothek suchen, die schon so etwas enthält, wie functional java, aber hier ging es ja nur „ums Prinzip“.

Und siehe, mit dem unveränderlichen Stack war die Implementierung auf einmal geradezu peinlich einfach: Keine veränderlichen Daten, kein Kopieren, keine Probleme.

import java.util.NoSuchElementException;
 
public class Coins {
 ...  
    private static void coins(Stack source, int leftSum, int rightSum,
                          Stack leftBag, Stack rightBag) {
        if (source.isEmpty()) {
            System.out.println("Solution: " + leftBag + " | " + rightBag);
        } else {
            int c = source.top();
            if (c <= leftSum) {
                coins(source.pop(), leftSum - c, rightSum, leftBag.push(c), rightBag);
            }
            if (c <= rightSum) {
                coins(source.pop(), leftSum, rightSum - c, leftBag, rightBag.push(c));
            }
        }
    }
 
    private static void coins(int... cs) {
        Stack source = new Empty();
        int sum = 0;
        for(int c : cs) {
            sum += c;
            source = source.push(c);
        }
        if (sum % 2 == 1) {
            System.out.println("Sum of coins is odd, no solutions");
        } else {
            coins(source, sum/2, sum/2, new Empty(), new Empty());
        }
    }
 
   public static void main(String... args) {
       coins(1,2,3,5,6,8,8,11);
   }
}

Solution: 11 8 3 | 8 6 5 2 1
Solution: 11 8 2 1 | 8 6 5 3
Solution: 11 8 3 | 8 6 5 2 1
Solution: 11 8 2 1 | 8 6 5 3
Solution: 11 6 5 | 8 8 3 2 1
Solution: 11 6 3 2 | 8 8 5 1
Solution: 11 5 3 2 1 | 8 8 6
Solution: 8 8 6 | 11 5 3 2 1
Solution: 8 8 5 1 | 11 6 3 2
Solution: 8 8 3 2 1 | 11 6 5
Solution: 8 6 5 3 | 11 8 2 1
Solution: 8 6 5 2 1 | 11 8 3
Solution: 8 6 5 3 | 11 8 2 1
Solution: 8 6 5 2 1 | 11 8 3

Wie man sieht funktioniert es, aber diese Implementierung hat natürlich auch ein paar Problemchen, z.B. sollte man die Lösungen besser „sammeln“ anstatt direkt ausgeben (Stichwort Separation of Concerns), und bei dieser Gelegenheit gleich Duplikate entfernen.

Ich habe mir den Spaß gemacht, das Ganze nach Scala zu übersetzen und die genannten Verbesserungen durchzuführen. Die Änderungen sind wirklich minimal, sieht man davon ab, dass ich jetzt List als Stack nutze, und die Ergebnisse in ein Set packe, anstatt sie einfach auszugeben.

object Coins {
  def coins(source:List[Int], leftSum:Int, rightSum:Int,
            leftBag:List[Int], rightBag:List[Int]): Set[(List[Int],List[Int])] =
  if (source.isEmpty) Set((leftBag, rightBag))
  else {
    val c = source.head
    val left= if (c <= leftSum)
            coins(source.tail, leftSum - c, rightSum, c :: leftBag, rightBag)
         else Set.empty
    val right = if (c <= rightSum)
             coins(source.tail, leftSum, rightSum - c, leftBag, c :: rightBag)
         else Set.empty
    left ++ right
  }

  def coins(cs:Int*) {
    val sum = cs.sum
    if (sum % 2 == 1) println("Sum of coins is odd, no solutions")
    else coins(cs.toList, sum/2, sum/2, Nil, Nil).foreach(println)
  }

  def main(args:Array[String]) {
    coins(1,2,3,5,6,8,8,11);
  }
}

(List(8, 6, 5, 3),List(11, 8, 2, 1))
(List(8, 8, 6),List(11, 5, 3, 2, 1))
(List(8, 8, 3, 2, 1),List(11, 6, 5))
(List(8, 8, 5, 1),List(11, 6, 3, 2))
(List(11, 8, 2, 1),List(8, 6, 5, 3))
(List(11, 6, 3, 2),List(8, 8, 5, 1))
(List(11, 6, 5),List(8, 8, 3, 2, 1))
(List(11, 5, 3, 2, 1),List(8, 8, 6))
(List(8, 6, 5, 2, 1),List(11, 8, 3))
(List(11, 8, 3),List(8, 6, 5, 2, 1))

Wie üblich ist der Scala-Code etwas kompakter, ohne unübersichtlich zu werden.

Was ist nun die Moral von der Geschicht‘?

  • Scala verändert die Art, wie ich denke, selbst wenn ich Java schreibe
  • Viele von Scalas Ideen funktionieren in Java, wenn auch etwas holpriger
  • Man sollte keine Angst davor haben, auf den passenden Containertyp zurückzugreifen, auch wenn er mal nicht in java.util zu finden ist
  • Man kann notfalls mit einem bescheidenen Codeschnipsel einen ganzen Blogeintrag füllen, wenn man die Sache nur philosophisch genug angeht.

Natürlich würde mich interessieren, ob ihr ähnliche Erfahrungen gemacht habt.

Advertisements

Ein Gedanke zu “In Java programmieren, in Scala denken

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s