[Haskell-cafe] Possible solution to the FGL naming/compatability issue

[Ivan Miljenovic]

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 at gmail.com
IvanMiljenovic.wordpress.com