On 24 November 2011 20:42, Ivan Lazar Miljenovic <[email protected]> wrote: > On 24 November 2011 20:33, Thomas DuBuisson <[email protected]> > wrote: >> All, >> >> 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 >> >> >> Cheers, >> Thomas >> >> P.S. Please do educate me if I simply missed or misunderstood some >> feature of FGL. > > Well, there *is* the NodeMap module, but I haven't really used it so > I'm not sure if it does what you want. > > We did start upon a version of FGL which had these type variables in > the class, but it got a little fiddly; the ability to have superclass > constraints should solve this but I haven't touched FGL for a while, > as I've been working on some other graph library code for planar > graphs, with the plan to take my experience from writing this library > into a "successor" to FGL. > > However, my experience with designing this planar graph library has > led me to using abstract (i.e. non-exported constructor) ID types for > nodes and edges and finding them rather useful, but then I'm more > concerned about the _structure_ of the graph rather than the items > stored within it. As such, I'd appreciate you explaining to me > (off-list is OK) why you want/need such a label -> node mapping so > that I can try and work out a way to incorporate such functionality.
To be more clear: we wanted superclass constraints because we had the main classes be of kind * with associated-types for the node and edge labels (which could possibly just be `()'); but to be able to do mapping over the nodes and edges we needed to be able to specify a mapping from "(g a b)" to "g a b" (where g is of kind * -> * -> *). -- Ivan Lazar Miljenovic [email protected] IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
