[Haskell-cafe] FGL custom node identification (Label -> Node lookup)

Thomas DuBuisson thomas.dubuisson at gmail.com
Thu Nov 24 10:33:21 CET 2011


The containers library has a somewhat primitive but certainly useful
Data.Graph library.  Building a graph with this library simultaneously
results in the lookup functions:

   m1 :: Vertex -> (node, key, [key])
   m2 :: key -> Maybe Vertex

(where 'key' is like FGL's 'label' but is assumed to be unique)

This is exactly what I wanted when building and analyzing a call graph
in FGL.  To that end, I started making a graph type that tracked label
to Node mappings, wrapping Data.Graph.Inductive.Gr,  and assuming the
labels are all unique.

The classes for such a graph actually aren't possible.  The ability to
build a mapping from a node's 'label' to the 'Node' requires extra
context (ex: Hashable, Ord, or at least Eq), but such context can not
be provided due to the typeclass construction.

Is there any chance we can change the Graph and DiaGraph classes to
expose the type variables 'a' and 'b'?

    class Graph gr a b where ...
    class (Graph gr) => DynGraph gr a b where ...

This would allow instances to provide the needed context:

    instance (Hashable a, Hashable b) => Graph UniqueLabel a b where
          buildGraph = ... some use of containers libraries that
require context ...
    lookupNode :: Hashable a => UniqueLabel a b -> a -> Node
    -- etc


P.S.  Please do educate me if I simply missed or misunderstood some
feature of FGL.

More information about the Haskell-Cafe mailing list