toying with subtyping

haskell_typeclass_subtyping.hs

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

module Graph where

import Data.IntMap as IM
import Data.Maybe

-- unsere "oberste" Klasse
class HasGraph g n e where
  getGraph :: g n e -> n -> [e]
  getNodes :: g n e -> [n]

-- eine "Vererbte Klasse"
class HasGraph g n e => WeightGraph g w n e where
  getWGraph :: g n e -> n -> [(e,w)]

-- Repräsentation unseres Graphen
data Node = Node Int
data Edge = Edge Node Node
data Weight = Weight Edge Int

-- Ein Beispielgraph. Statt Liste auch Unboxed-Vector etc. einsetzen
data SimpleGraph n e = SGraph [n] (IntMap [e])
instance HasGraph SimpleGraph Node Edge where
  getGraph (SGraph node edge) (Node n) = fromJust $ IM.lookup n edge
  getNodes (SGraph n _) = n

-- Ein Gewichteter Beispielgraph
data WeightedGraph w n e = WGraph [n] (IntMap [(e,w)])
instance HasGraph (WeightedGraph Weight) Node Edge where
  getGraph (WGraph node edge) (Node n) = fst <$> fromJust (IM.lookup n edge)
  getNodes (WGraph n _) = n
instance WeightGraph (WeightedGraph Weight) Weight Node Edge where
  getWGraph (WGraph node edge) (Node n) = fromJust $ IM.lookup n edge


-- Beispiel für generische Funktionen, die auf allen Graphen funktionieren
getVertexCount :: HasGraph g n e => g n e-> Int
getVertexCount g = length $ getNodes g

-- Beispiel für generische Funktionen, die einen min. gewichteten Graphen brauchen, i.e. w taucht in der typsignatur auf
getShortestPathWeighted :: WeightGraph g w n e => g n e -> w
getShortestPathWeighted = undefined


-- Man könnte noch weiter gehen und z.b. das Int heraus faktorisieren, das ganze dann zu einem Funktor machen etc.