Schachteln für Fortgeschrittene


Angeregt von dieser Frage auf Stackoverflow will ich mich heute mit geschachtelten Listen beschäftigen: Kann man eine Methode schreiben, die sowohl eine Liste von Ints wie auch eine Liste von Int-Listen wie auch eine Liste von Listen von Int-Listen u.s.w. aufsummieren kann? Sicher, das geht auch in Java – allerdings nicht typsicher: Da es dort keine Möglichkeit gibt, einen allgemeinen „Listen-Stapel-Typ“ zu definieren, muss gecastet werden, und das wiederum heißt, das Laufzeitfehler auftreten können, wenn ein ungeeignetes Objekt (sagen wir eine String-Liste) übergeben wird.

Wie sieht die Haskell-Lösung aus?

class Summable a where
  total :: a -> Int

instance Summable Int where
  total = id  

instance Summable x => Summable [x] where
  total = sum . map total  

total ([[[1,2,3],[4,5]],[[6],[7,8,9,10]]] :: [[[Int]]])
--55

Aha, Typklassen! Wir definieren eine Typklasse „Summable“, die eine Funktion „total“ zum Aufsummieren enthält. Die Instanz für Int ist trivial: Wir geben einfach die Zahl selbst zurück (man hätte dafür auch total x = x schreiben können). Interessanter ist die Instanz für Listen, die eine sogenannte Context-Bound enthält: Wenn a in der Klasse Summable ist, dann ist auch eine Liste von a in der Klasse – genau die Art von „Rekursivität“, die wir brauchen. Deshalb darf man in der Definition von total auch die Funktion total auf die Elemente anwenden, da man ja weiß, dass sie auch Summable sind. In der letzten Zeile wird die Funktion ausprobiert (dass man u.U. die Typangabe :: [[[Int]]] braucht, hat nichts mit unseren Typklassen zu tun, sondern ist der „Monomorphismus-Restriktion“ geschuldet, und wäre bei nicht-numerischen Typen nicht notwendig).

Wie setzt man das nun in Scala um? Ich habe mich zuerst mit einer typklassenartigen Implementierung versucht, bin aber nicht so recht weitergekommen. Am Ende hat dann eine etwas direktere Vorgehensweise zum Ziel geführt:

object nestedTest {
  
  case class Summable(total:Int)
   
  implicit def intSummable(i:Int) = Summable(i)
  
  implicit def listSummable[T <% Summable](list:List[T]) = Summable(list.map(_.total).sum)
  
  def total[T <% Summable](t:T) = t.total
  
  def main(args: Array[String]) {
    println(total(1))
    println(total(List(1,2,3)))
    println(total(List(List(1),List(2,3))))
    //println(total(List(List("a"),List("b","c")))) 
    //--> error: No implicit view available from List[List[java.lang.String]] => nestedTest.Summable.
  }
}

Summable ist jetzt keine Typklasse, sondern einfach ein Wrapper um Int. Dann definiere ich entsprechende Konvertierungen. Wieder ist die Umwandlung von Int nicht besonders spannend, dafür die Definition der List-Variante. Der entscheidende Trick ist die Verwendung einer View-Bound T <% Summable. Das heißt, dass T in ein Summable "umwandelbar" sein muss, und genau das ist der Trick, um Scala die gewünschte "Rekursivität" beizubringen. Durch die Garantie der View-Bound ist es erlaubt, map(_.total) zu schreiben, denn wir wissen ja, dass T in ein Summable konvertiert werden kann, und Summable hat ein Feld namens total. Für die Bequemlichkeit definieren wir noch eine Top-Level-Funktion für total, um dem Anwender das Hantieren mit Summable zu ersparen. In der main-Methode werden nun verschiedene Varianten ausprobiert. Ein Aufruf mit einem unpassenden Argument scheitert, und das sogar mit einer recht verständlichen Fehlermeldung.

Ich hoffe, dass das Beispiel gezeigt hat, dass Scalas Typsystem dem von Java auch bei recht praktischen Aufgabestellungen überlegen ist, auch wenn man manchmal etwas frickeln muss. Haskell glänzt hier mit einer sehr einfachen Variante, aber es gibt auch Konstrukte, die sich besser mit Scala implementieren lassen (z.B. alles mit variabler Anzahl Argumente).

Ich fasse schon einmal den guten Vorsatz, das Blog nächstes Jahr nicht ganz so stiefmütterlich zu behandeln. An spannenden Themen soll es nicht mangeln: Da wäre das gerade frisch releaste Ceylon (allerdings mit noch enttäuschenden Funktionsumfang), Bauarbeiten an Scala und Java, die tolle Sprache Frege, die langsam erwachsen wird und ihr Vorbild Haskell, bei dem auch interessante Neuerungen anstehen, wenn man Simon Peyton Jones glaubt.

Dann wünsche ich allen ein Frohes Fest, einen Guten Rutsch und ein erfolgreiches 2012!

Advertisements

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