Lösungen: Pattern Matching

  1. Die wohl einfachste Lösung:
    def size(xs: List[Int]): Int =
      if (xs.isEmpty) 0 else 1+size(xs.tail)
    

    Mit Pattern Matching:

    def size(xs: List[Int]): Int = xs match {
      case Nil => 0
      case _ :: tail => 1+size(tail)
    }
    

    Bei diesen Lösungen kann es aber zu einem StackOverflowError kommen wenn die Listen nur lang genug sind. Deshalb sollte die Tail-rekursive Lösung bevorzugt werden:

    def size(xs: List[Int], acc: Int = 0): Int = xs match {
      case Nil => acc
      case _ :: tail => size(tail, acc+1)
    }
    
  2. Gleiche Lösungsstrategie wie bei der vorherigen Aufgabe:
    def sum(xs: List[Int], acc: Int = 0): Int = xs match {
      case Nil => acc
      case head :: tail => sum(tail, acc+head)
    }
    
  3. Wenn wir die Liste umdrehen und dann an das Original hängen haben wir es einfach:
    def toPalindrome(xs: List[Int]): List[Int] = {
      def reverse(xs: List[Int], ys: List[Int]): List[Int] =
        if (xs.isEmpty) ys else reverse(xs.tail, xs.head :: ys)
      xs ++ reverse(xs, Nil)
    }
    
  4. Eine Lösung mit einer lokalen Methode um über die Liste zu iterieren:
    def intersperse(sep: String, xs: List[String]): String = {
      def loop(xs: List[String], s: String): String = xs match {
        case Nil => s
        case head :: Nil => s+head
        case head :: tail => loop(tail, s+head+sep)
      }
      loop(xs, "")
    }
    
  5. Wir benötigen eine List[Any], da wir durch die Verschachtelungen nicht wissen können was für Elemente in der Liste vorliegen.
    def flatten(xs: List[Any]): List[Any] = xs match {
      case Nil => Nil
      case (head: List[_]) :: tail => flatten(head) ::: flatten(tail)
      case  head :: tail => head :: flatten(tail)
    }
    
  6. Hier müssen wir uns sogar zweier lokalen Methoden bedienen. Eine, die über die Ausgangsliste iteriert und eine Andere, die die Elemente vervielfältigt.
    def multiplicateElems(n: Int, xs: List[Int]) = {
      def mul(i: Int, elem: Int, xs: List[Int]): List[Int] =
        if (i == 0) xs else mul(i-1, elem, elem :: xs)
      def loop(xs: List[Int], ys: List[Int]): List[Int] =
        if (xs.isEmpty) ys else loop(xs.tail, mul(n, xs.head, Nil) ::: ys)
      loop(xs, Nil).reverse
    }
    
  7. Wir müssen hier aufpassen, dass wir alle gruppierten Elemente wieder umdrehen, da die Listen falsch herum aufgebaut werden.
    def group(n: Int, xs: List[Int]): List[List[Int]] = {
      def loop(i: Int, xs: List[Int], ys: List[Int], zs: List[List[Int]]): List[List[Int]] =
        if (xs.isEmpty) ys.reverse :: zs
        else if (i == 0) loop(n, xs, Nil, ys.reverse :: zs)
        else loop(i-1, xs.tail, xs.head :: ys, zs)
      loop(n, xs, Nil, Nil).reverse
    }
    
  8. Das ist nicht schwer. Wir müssen nur schauen ob ein Element in der neuen Liste schon vorhanden ist.
    def compress(xs: List[Int]): List[Int] = {
      def loop(xs: List[Int], ys: List[Int]): List[Int] =
        if (xs.isEmpty) ys
        else if (ys contains xs.head) loop(xs.tail, ys)
        else loop(xs.tail, xs.head :: ys)
      loop(xs, Nil).reverse
    }
    

Noch eine Anmerkung zum Schluss: Das ständige Umdrehen der Liste mag nicht besonders schön sein, aber es ist die einfachste Möglichkeit mit der wir unsere Listen korrekt aufbauen können. Die List-Implementierung von Scala benutzt intern ein veränderliches letzten Element, das es erlaubt neue Elemente effizient ans Ende zu hängen.

Da wir ja aber das funktionale Programmieren lernen wollen, bestehen wir lieber auf eine unveränderliche Liste und drehen sie am Schluss einfach um.

Advertisements

2 comments so far

  1. miraculi on

    @Aufgabe 1: typ-generische Lösung mit map reduce:

    def size(xs: Seq[Any]): Int = { xs map (Any => 1) sum }

    • antoras on

      Das geht natürlich auch. Da ich Funktionen höherer Ordnung aber noch nicht angesprochen habe, habe ich diese Lösung auch nicht angegeben.

      Mir fällt gerade auf, dass ich z.T. parametrisierte Methoden angegeben habe. Werde ich gleich noch ändern.


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

%d Bloggern gefällt das: