Kruskal in Haskell und Scala


Nein, heute geht es nicht um Zungenbrecher, sondern um Minimale Spannbäume. Ich hatte mich schon einmal damit beschäftigt, wobei ich den Algorithmus von Prim in Scala implementiert hatte.

Heute habe ich kleine Fingerübung den anderen bekannten Algorithmus, nämlich den von Kruskal, in Haskell implementiert.

module Kruskal (
   Edge(..),
   kruskal
) where

import Data.List(sort)
import Data.Set (Set, member, fromList, insert, union)

data Edge a = Edge a a Double deriving Show

instance (Eq a) => Eq (Edge a) where
  Edge x1 y1 z1 == Edge x2 y2 z2 = x1 == x2 && y1 == y2 && z1 == z2

instance Eq a => Ord (Edge a) where
  (Edge _ _ x) `compare` (Edge _ _ y) = x `compare` y

kruskal :: Ord a => [Edge a] -> [Edge a]
kruskal = fst . foldl mst ([],[]) . sort

mst :: Ord a => ([Edge a],[Set a]) -> Edge a -> ([Edge a],[Set a])
mst (es, sets) e@(Edge p q _) = step $ extract sets where
   step (rest, Nothing, Nothing) = (e : es, fromList [p,q] : rest)
   step (rest, Just ps, Nothing) = (e : es, q `insert` ps : rest)
   step (rest, Nothing, Just qs) = (e : es, p `insert` qs : rest)
   step (rest, Just ps, Just qs) | ps == qs = (es, sets) --circle
                                 | otherwise = (e : es, ps `union` qs : rest)
   extract = foldr f ([], Nothing, Nothing) where
       f s (list, setp, setq) =
            let list' = if member p s || member q s then list else s:list
                setp' = if member p s then Just s else setp
                setq' = if member q s then Just s else setq
            in (list', setp', setq')

Ich will nicht allzu sehr auf die Details eingehen, denn meine Haskell-Kenntnisse sind noch nicht auf einem Niveau, in dem ich wirklich idiomatischen Code schreiben und auch noch verständlich erklären könnte.

Zuerst habe ich einen Typ „Edge“ für die Kanten definiert, wobei ich offen gelassen habe, wie man die Knoten darstellt (deshalb überall die Typvariable a). Bei den Kantenlängen habe ich mich auf Double festgelegt.

Danach habe ich für Edge die Typklassen Eq und Ord implementiert, so dass ich in der Funktion kruskal die Kantenliste sortieren kann. Über ein foldl gehe ich dann die sortierten Kanten durch und sammle dabei alle Informationen die ich brauche. Dazu gibt es ein Paar, das im ersten Element alle Kanten sammelt, die zum Spannbaum gehören, und als zweites Element eine Liste von Knoten-Sets, die die einzelnen Teilgraphen repräsentieren.

Für eine neue Kante schaue ich dann mit der Funktion mst, ob sie isoliert ist (dann wird ein neues Set hinzugefügt), ob beide Endpunkte bereits in ein und demselben Set liegen (dann würde ein Zyklus entstehen, also wird diese Kante verworfen), ob ein Endpunkt zu einem Set gehört (das dann um den anderen vergrößert wird) oder beide Endpunkte zu unterschiedlichen Sets (dann werden beide Sets vereinigt). Die Hilfsfunktion extract findet die entsprechenden Sets in der Liste, und liefert auch die Restliste ohne die Sets zurück.

Ruft man den Code mit dem Beispiel aus dem oben verlinkten Wikipedia-Artikel auf, kommt auch das erwartete Ergebnis heraus:

main = print $ kruskal [Edge 'A' 'B' 7, Edge 'A' 'D' 5, 
   Edge 'B' 'C' 8, Edge 'B' 'D' 9, Edge 'B' 'E' 7, 
   Edge 'C' 'E' 5, Edge 'D' 'E' 15, Edge 'D' 'F' 6, 
   Edge 'E' 'F' 8, Edge 'E' 'G' 9, Edge 'F' 'G' 11]

-- [Edge 'E' 'G' 9.0,Edge 'B' 'E' 7.0,Edge 'A' 'B' 7.0,
--  Edge 'D' 'F' 6.0,Edge 'C' 'E' 5.0,Edge 'A' 'D' 5.0]

Ich denke, das ist für einen Haskell-Anfänger ganz brauchbar. Für Anregungen wäre ich wie immer dankbar.

Hier ist die Scala-Version:

object Kruskal {

  case class Edge[A](v1:A, v2:A, d:Double)

  type LE[A] = List[Edge[A]]
  type LS[A] = List[Set[A]]
  type OS[A] = Option[Set[A]]

  def kruskal[A](list: LE[A]) = list.sortBy(_.d).foldLeft((Nil:LE[A],Nil:LS[A]))(mst)._1

  def mst[A](t:(LE[A], LS[A]), e:Edge[A]) = (t,e) match {
    case ((es, sets), Edge(p,q,_)) =>

      def step(t:(LS[A], OS[A], OS[A])) = t match {
        case (rest, None, None) => (e :: es, Set(p,q) :: rest)
        case (rest, Some(ps), None) => (e :: es, ps + q :: rest)
        case (rest, None, Some(qs)) => (e :: es, qs + p :: rest)
        case (rest, Some(ps), Some(qs)) => if (ps == qs) (es, sets) //circle
                                           else (e :: es, ps ++ qs :: rest)
      }

      val extract = sets.foldRight((Nil:LS[A], None:OS[A], None:OS[A]))
      {(s:Set[A], t:(LS[A],OS[A],OS[A])) => t match
       { case (list, setp, setq) =>
            val sp = s.contains(p)
            val sq = s.contains(q)
            (if (sp || sq) list else s :: list,
             if (sp) Some(s) else setp,
             if (sq) Some(s) else setq)
        }}

      step(extract)
  }

  def main(args:Array[String]) {
    println(kruskal(
        List(Edge('A,'B,7), Edge('A,'D,5),Edge('B,'C,8), Edge('B,'D,9),
             Edge('B,'E,7), Edge('C,'E,5), Edge('D,'E,15), Edge('D,'F,6),
             Edge('E,'F,8), Edge('E,'G, 9), Edge('F,'G,11))))
  }

}

Die „Übersetzung“ ist bewußt dicht am Original geblieben, was etwas zu Lasten der Lesbarkeit geht. Wie man sieht, sind die Fallklassen den Haskell-Typen durchaus ebenbürtig. Nur die vielen Typangaben stören, auch wenn sich das wie hier durch Typ-Aliase etwas entschärfen läßt. Ein Haskell-Feature, das ich hier vermisst habe, war Pattern-Matching direkt auf den Argumentlisten von Funktionen. In Scala hat man keine andere Wahl, als die Methoden-Argumente über ein separates match auseinanderzunehmen, was Platz kostet und unübersichtlicher ist.

Es war auffällig, dass das Umsetzen der Haskell-Strukturen nach Scala recht problemlos verlief, aber viel Zeit mit der Typ-Frickelei verloren gegangen ist. Die Fehlermeldungen von Scala finde ich im allgemeinen ganz gut, aber wenn es um etwas kompliziertere Typ-Spielereien geht, waren sie nicht besonders hilfreich. Zumindest bin ich mit den „berüchtigten“ Fehlermeldungen von Haskell bei diesem Problem besser zurechtgekommen.

PS: Das war übrigens mein hundertster Blog-Eintrag. Auch wenn es immer mal wieder längere Pausen zwischen den Artikeln gibt, sind mir die Ideen noch lange nicht ausgegangen. Manches muss auch erst ein bisschen köcheln, bis es präsentationsfähig ist. Ich hoffe, ihr bleibt mir gewogen. Und falls ich zuviel obkures Zeug abliefere, sagt mir, über welche „normalen“ Themen ich noch schreiben soll.

Nachtrag: Im Folgebeitrag habe ich die Scala Version noch etwas beschleuningt.

Advertisements

Ein Gedanke zu “Kruskal in Haskell und Scala

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