Last night (AEST), Edward Kmett semi-convinced (in the sense that I'm not sure whether his examples are really those that someone would want/need or just thinking of possible future problems) me that some users may have a need for FGL to keep having explicit graphs with kind * -> * -> *. With his prompting, I may have a possible solution: duplicate the classes. We would have an InductiveGraph class (call it the parametric version) that requires graphs to have kind * -> * -> *, and then another class (call it the extended version) that removes this restriction. The parametric version would be closer to a drop-in replacement to the current FGL setup (see below for more details) and the extended one would provide all of the functionality requested, with some kind of semi-automatic lifting/unlifting for graph types that are instances of both. Now, this parametric version will still not be a drop-in for the current FGL, for several reasons: * I want to have one overall InductiveGraph class rather than two separate Graph and DynGraph classes * Context will still be an actual data type rather than a 4-tuple and LEdge would be come (Edge, Label) rather than (Node, Node, Label) [I'm still debating whether to keep Edge as a datatype as needed for the Type Familiy version or if it should just be a tuple). * Some function names will be changed (e.g. fromContexts rather than buildGr). * The Data.Graph.Inductive.Query stuff is going to be split out into its own separate library, the Data.Graph.Inductive.Graphviz stuff is going to be removed, etc. * With the removal of the sub-libraries, I'm seriously considering moving the class definitions from Data.Graph.Inductive.Graph to just Data.Graph.Inductive. There are also some caveats/design decisions with this solution: * There will obviously be duplication. With that said, do we try to make the two classes semi-drop-ins (same class name, methods, etc. but with different types) or think up new method names for the extended version? * How transparently can/will we make the lifting/unlifting? * If we want the parametric version to still have the ability to specify a custom node type, then it will still need either MPTCs + fundeps or Type Families (i.e. extensions); otherwise we stick with the current "type Node = Int" (or maybe replace it with some opaque abstract type down the track as suggested by Heinrich Apfelmus). * If we want to provide the ability to restrict the types of the labels in the parametric version, then we would need MPTCs (Type Families won't work since the label types won't be part of the class definition then unless we use MPTCs, and in that case there's not really any point in using Type Families). Thus we once again need extensions. * My semi-end goal is to build a proper hierarchy of graph types/libraries, such that the only thing FGL provides is the extra aspect/concept of inductive graphs. If we extend this parametric vs extended split down to the set of base graph classes, then we're going to have even more duplication and this kind of setup (where "Foo depends on Bar" means "class (Bar a) => Foo a where ..."): - fgl-parametric will depend on graph-parametric - fgl-extended will depend on graph-extended - There will be lifting/unlifting between graph-parametric and graph-extended - There will be lifting/unlifting between fgl-parametric and fgl-extended As such, an FGL graph of kind * -> * -> * being treated as an extended graph will have two possible ways (depending on the function in question) will have two graph hierarchies two choose from, and two possible points at which it can be lifted/unlifted (at the graph level and the fgl level). This could get confusing. That said, there is one other benefit of this parametric vs extended split: the types of the mapping functions in http://code.haskell.org/FGL/fgl/Data/Graph/Inductive/Graph.hs won't be as weird... So, what are people's thoughts/opinions on this kind of setup? Note that I haven't started coding it yet, so I'm not sure how well it will work in practice... -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com