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.

Advertisements

2 Gedanken zu “Listen-Urschleim: 99 Scala-Probleme

  1. Ist ja nun schon 2 Monate her; zur Frage @tailrec war heute/gestern auf der Mailingliste ein ähnlicher Fall, wo der Compiler einfach gelogen hat. 🙂

    Wahrscheinlich hast Du es schon gesehen: http://scala-programming-language.1934581.n4.nabble.com/Is-this-a-taill-call-td3178042.html
    Hier wäre meine Lösung.

    @tailrec
     def isPalindrome [A] (l: List [A]) : Boolean =              
         if (l.isEmpty || l.tail.isEmpty) true else            
         (l.head == l.last) && isPalindrome (l.slice (1, l.size-1))
    
  2. Ich denke, die last- und slice-Aufrufe bei deiner Version sind furchtbar inperformant, jedenfalls bei Listen. Eine direkte endrekursive Implementierung mit Rekursionstiefe n/2 wäre:

      def isPalindrome[T](list: List[T]) = {
        @tailrec
        def loop(full:List[T], half:List[T], accu:List[T]):Boolean = full match {
          case Nil => half == accu
          case _ :: Nil => half.tail == accu
          case _ :: _ :: fullTail => loop(fullTail, half.tail, half.head :: accu)
        }
        loop(list, list, Nil)
      }
    

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