Apologies for the fuzzy title - I don’t really know what exactly I’m looking for, so it’s hard to verbalize…
My toy problem is this: I want to come up with a minimalist abstraction for graphs in order to generate graphviz/dot renderings for arbitrary data representations. In general, these may come in two flavors:
- edges embedded in the data type (e.g. tree nodes)
- edges from an external data structure (e.g. an incidence list)
In Scala, I might do something like this:
trait Graph[A] {
def edges(v: A): List[A]
}
// instance for an "embedded" case
implicit def binTreeGraph[A]: Graph[BinTree[A]] = {
case BinLeaf(_) => List.empty
case BinINode(_, l, r) => List(l, r)
}
// scaffolding for an "external" case
type IncidenceList[A] = List[(A, List[A])]
def incidenceGraph[A](incs: IncidenceList[A]): Graph[A] =
(v: A) => incs.find(_._1 == v).fold(List.empty[A])(_._2)
// usage
def printEdges[A : Graph](a: A): Unit = ???
printEdges(BinINode(2, BinLeaf(1), BinLeaf(3)): BinTree[Int]) // embedded
printEdges("a")(incidenceGraph(List("a" -> List("b", "c")))) // external
I’m wondering how to tackle this in Haskell. Naively going with a type class approach and the same API…
class Graph a where
edges :: a -> [a]
…I can easily write instances for embedded cases. But what about the external variants? The best I could come up with is this:
type IncidenceList a = [(a, [a])]
class IncidenceListProvider a where
incidences :: IncidenceList a
newtype Vertex a = Vertex a deriving (Eq, Show)
instance (IncidenceListProvider a, Eq a) => Graph (Vertex a) where
edges (Vertex v) = Vertex <$> fromMaybe [] (lookup v incidences)
This kind of works…
newtype StrV = StrV Text deriving (Eq, Show)
instance IncidenceListProvider StrV where
incidences = [(StrV "a", [StrV "a", StrV "b"]), (StrV "b", [StrV "c"])]
print $ edges (Vertex (StrV "a"))
…but it feels odd and convoluted. I’m sure there’s better approaches. Any suggestions?