Listen-Urschleim: 99 Scala-Probleme

Hatte ich eigentlich schon die schöne Aufgabensammlung 99 Scala-Probleme erwähnt? Dann hole ich das hiermit nach und lege sie allen Scala-Adepten ans Herz.

Die ersten 28 Aufgaben beschäftigen sich mit Listen. Inzwischen habe ich genug Scala-Erfahrung, um das ziemlich problemlos hinzubekommen. Damit es trotzdem eine kleine Herausforderung wird, habe ich mir noch zwei nette Zusatzbedinungen ausgedacht:

  1. Ich verwende meinen eigenen, wirklich strunzdoofen Listentyp
  2. Alle meine Lösungen müssen endrekursiv sein

Den einzigen kleinen Luxus, den mein Listentyp bietet, ist die apply()-Methode zum bequemen Initialisieren:

sealed trait LIST[+T]

case class CONS[T](car: T, cdr: LIST[T]) extends LIST[T]

case object NIL extends LIST[Nothing] 

object LIST {
  def apply[T](seq:T*):LIST[T] =
    if (seq.isEmpty) NIL else CONS(seq.head, LIST(seq.tail:_*))
}

Die ersten drei Methoden sind leicht:

import scala.annotation.tailrec

object NinetyNine {

  //P01 (*) Find the last element of a list
  @tailrec
  def last[T](list: LIST[T]): T = list match {
    case CONS(x, NIL) => x
    case CONS(_, xs) => last(xs)
    case NIL => error("last on empty LIST")
  }

  //P02 (*) Find the last but one element of a list.
  @tailrec
  def penultimate[T](list: LIST[T]): T = list match {
    case CONS(x, CONS(_ , NIL)) => x
    case CONS(_, xs) => penultimate(xs)
    case _ => error("not enough elements in LIST")
  }

  //P03 (*) Find the Kth element of a list.
  @tailrec
  def nth[T](n: Int, list:LIST[T]): T = list match {
    case CONS(x, _) if n == 0 => x
    case CONS(_, xs) if n > 0 => nth(n-1, xs)
    case _ => error("not enough elements in LIST or negative index")
  }
...

Methode Nummer 4 und 5 könnte man auch in diesem Stil schreiben, aber dann sind sie nicht mehr endrekursiv. Die Standardlösung für solchen Fälle ist eine lokale Methode mit (meist) einem zusätzlichen Argument, dem „Akkumulator“, der den Zwischenstand des Endergebnisses speichert. Die Palindrom-Methode Nummer 6 bedient sich frech bei Nummer 5, denn mir ist beim besten Willen keine effizientere Implementierung eingefallen.

...
  //P04 (*) Find the number of elements of a list.
  def length(list:LIST[_]): Int = {
    @tailrec
    def len(li:LIST[_], count: Int): Int = li match {
      case CONS(_, xs) => len(xs, count + 1)
      case NIL => count
    }
    len(list, 0)
  }

  //P05 (*) Reverse a list.
  def reverse[T](list:LIST[T]):LIST[T] = {
    @tailrec
    def rev(rest:LIST[T], accu:LIST[T]): LIST[T] = rest match {
      case NIL => accu
      case CONS(x, xs) => rev(xs, CONS(x, accu))
    }
    rev(list, NIL)
  }

  //P06 (*) Find out whether a list is a palindrome.
  def isPalindrome[T](list: LIST[T]) = list == reverse(list)
...

Methode Nummer 7 war dann schon etwas schwieriger, aber wenn man erst einmal eine Methode zum Aneinanderhängen von Listen hat, wird es leichter. Wem die Pattern-Matching-Syntax mit dem @-Klammeraffen spanisch vorkommt, findet sie am Ende dieses Artikels erklärt. Ehrlich gesagt ist mir nicht ganz klar, warum flatten trotz des zweiten case-Statements als endrekursiv durchgeht. Jedenfalls ziehe ich vor dem Scala-Compiler meinen Hut, der bei dieser Optimierung anscheinend ganze Arbeit leistet.

...
  //helper method
  def append[T](aList: LIST[T], bList: LIST[T]): LIST[T] = {
    @tailrec
    def app(aList: LIST[T], bList: LIST[T]): LIST[T] = aList match {
      case CONS(a, as) => app(as, CONS(a, bList))
      case NIL => bList
    }
    app(reverse(aList), bList)
  }  

  //P07 (**) Flatten a nested list structure.
  @tailrec
  def flatten(list: LIST[Any]): LIST[Any] = list match {
    case CONS(NIL, xs) => flatten(xs)
    case CONS(x@CONS(_,_), xs) => append(flatten(x), flatten(xs))
    case CONS(x, xs) => CONS(x, flatten(xs))
    case NIL => NIL
  }
...

Die nächsten drei Methoden beschäftigen sich mit verschiedenen Arten der „Kompression“. Wieder begegnen uns die lokalen Methoden mit ihren „Akkus“:

...
  //P08 (**) Eliminate consecutive duplicates of list elements.
  @tailrec
  def compress[T](list: LIST[T]): LIST[T] = list match {
    case NIL => NIL
    case CONS(a, as@CONS(b, _)) if a == b => compress(as)
    case CONS(a, as) => CONS(a, compress(as))
  }

  //P09 (**) Pack consecutive duplicates of list elements into sublists.
  def pack[T](list: LIST[T]): LIST[LIST[T]] = {
    @tailrec
    def pck[T](list: LIST[T], accu: LIST[LIST[T]]): LIST[LIST[T]] = (list, accu) match {
      case (NIL, _) => reverse(accu)
      case (CONS(a, as), CONS(bbs@CONS(b, bs), cs)) if a == b => pck(as, CONS(CONS(a,bbs),cs))
      case (CONS(a,as), _) => pck(as, CONS(CONS(a, NIL), accu))
    }
    pck(list, NIL)
  }

  //P10 (*) Run-length encoding of a list.
  def encode[T](list: LIST[T]): LIST[(Int,T)] = {
    @tailrec
    def rle[T](list: LIST[T], accu: LIST[(Int,T)]): LIST[(Int,T)] = (list, accu) match {
      case (NIL, _) => reverse(accu)
      case (CONS(a, as), CONS((n, b), cs)) if a == b => rle(as, CONS((n+1,b), cs))
      case (CONS(a,as), _) => rle(as, CONS((1, a), accu))
    }
    rle(list, NIL)
  }
...

Ich denke, das ist genug für heute. Natürlich sollte man das ganze auch noch testen:

...
  def main(args:Array[String]) {
    require(last(LIST(1, 1, 2, 3, 5, 8)) == 8, "last")
    require(penultimate(LIST(1, 1, 2, 3, 5, 8)) == 5, "penultimate")
    require(nth(2, LIST(1, 1, 2, 3, 5, 8)) == 2, "nth")
    require(length(LIST(1, 1, 2, 3, 5, 8)) == 6, "length")
    require(reverse(LIST(1, 1, 2, 3, 5, 8)) == LIST(8, 5, 3, 2, 1, 1), "reverse")
    require(isPalindrome(LIST(1, 2, 3, 2, 1)), "isPalindrome")
    require(flatten(LIST(LIST(1, 1), 2, LIST(3, LIST(5, 8)))) ==
            LIST(1, 1, 2, 3, 5, 8), "flatten")
    require(compress(LIST('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))==
            LIST('a, 'b, 'c, 'a, 'd, 'e), "compress")
    require(pack(LIST('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) ==
            LIST(LIST('a, 'a, 'a, 'a), LIST('b), LIST('c, 'c), LIST('a, 'a),
            LIST('d), LIST('e, 'e, 'e, 'e)), "pack")
    require(encode(LIST('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) ==
            LIST((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)), "encode")
    println("SUCCESS!!!")
  }
}

Dass man mit so rudimentären Klassen trotzdem relativ gut zurecht kommt (auch wenn es manchmal etwas langatmig wird), zeigt eindrucksvoll die Power, die hinter dem Pattern-Matching und Fallklassen steckt. Natürlich könnte man stattdessen auch einen kleinen Satz Funktionen höherer Ordnung definieren (map, foldLeft und foldRight würden sich hier anbieten) und damit weiterarbeiten.

Ich hoffe, ich habe ein wenig den Ehrgeiz geweckt, euch selbst einmal an den Aufgaben zu versuchen (egal ob nun mit List oder LIST), und vielleicht konntet ihr euch ja auch den einen oder anderen Trick abschauen.

Wie immer sind Verbesserungsvorschläge willkommen.

Werbeanzeigen

Alternativen

In manchen Fällen braucht man Alternativen, in diesem hier zu Option und zu Either. Denn damit ist es nur umständlich auzudrücken, dass von zwei Werten mindestestens einer vorhanden sein muss, z.B. wenn wenigstens Vor- oder Nachname eingegeben werden muss, aber auch beides erlaubt ist. Ein anderes Beispiel wäre, wenn man von einer Funktion entweder ein Resultat oder einen Fehler (bis hierhin wäre das ein typischer Fall für Either) oder aber sowohl ein Resultat wie auch eine Warnung zurückbekommen kann.

Soetwas mit den vorhandenen Mitteln auszudrücken ist nicht ganz einfach: Ein Tupel von zwei Options erlaubt auch die „verbotene“ (None, None)-Kombination, und da Either nicht beide Werte gleichzeitig abbilden kann, landet man damit bei Konstruktionen wie Either[Either[A,B], Tuple2[A,B]], mit dem kein Mensch vernünftig arbeiten kann. Dabei ist ein selbstgestrickter Alternative-Type nicht schwer zu schreiben:

sealed trait Alternative[+A,+B] {
  def leftOption: Option[A] = this match {
    case First(a) => Some(a)
    case Second(_) => None
    case Both(a, _) => Some(a)
  }

  def rightOption: Option[B] = this match {
    case First(_) => None
    case Second(b) => Some(b)
    case Both(_, b) => Some(b)
  }

  def bothOptions= (leftOption, rightOption)

  //more efficient implementation than using mapLeft and then mapRight
  def map[AA,BB](fa: A => AA, fb: B => BB):Alternative[AA,BB] = this match {
    case First(a) => First(fa(a))
    case Second(b) => Second(fb(b))
    case Both(a, b) => Both(fa(a),fb(b))
  }

  def mapLeft[AA] (fa: A => AA):Alternative[AA, B] = this match {
    case First(a) => First(fa(a))
    case Second(b) => Second(b)
    case Both(a, b) => Both(fa(a),b)
  }

  def mapRight[BB] (fb: B => BB): Alternative[A, BB] = this match {
    case First(a) => First(a)
    case Second(b) => Second(fb(b))
    case Both(a, b) => Both(a,fb(b))
  }

  def orElse[AA >: A, BB >: B](that:Alternative[AA,BB]) = (this,that) match {
    case (First(a),Second(b)) => Both(a,b)
    case (First(a),Both(_,b)) => Both(a,b)
    case (Second(b),First(a)) => Both(a,b)
    case (Second(b),Both(a,_)) => Both(a,b)
    case _ => this
  }

  def leftOrElse[AA >: A](aDefault:AA) = leftOption.getOrElse(aDefault)
  def rightOrElse[BB >: B](bDefault:BB) = rightOption.getOrElse(bDefault)
  def getOrElse[AA >: A, BB >: B](aDefault:AA, bDefault:BB) =
    (leftOrElse(aDefault), rightOrElse(bDefault))
}

case class First[+A,+B](_1:A) extends Alternative[A,B]
case class Second[+A,+B](_2:B) extends Alternative[A,B]
case class Both[+A,+B](_1:A, _2:B) extends Alternative[A,B]

Natürlich ist das nur eine von vielen Möglichkeiten, so einen Typ zu implementieren, und man könnte natürlich noch viele nützliche Sachen hinzufügen. Man kann in der Implementierung sehr schön sehen, wie sehr Fallklassen und Pattern Matching unser Leben erleichtern können. Die einzige kleine Herausforderung war, die Varianzen richtig hinzubekommen, aber da half ein bisschen Kiebitzen bei unseren „Vorbildern“ Option und Either.

Ich wollte mit diesem Beispiel zeigen, dass man nicht auf Krampf irgendwelche wilden Konstrukte mit Klassen wie Option oder Either verwenden sollte, wenn sie nicht wirklich zur Aufgabenstellung passen, weil es leicht ist, sich selbst eine passende Variante zu schreiben. Viel Spaß beim Ausprobieren!