[Haskell-cafe] Please check your dependencies on fgl

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Mon Jun 7 18:51:59 EDT 2010

Don Stewart <dons at galois.com> writes:

> ivan.miljenovic:
>> We considered giving it a new name (fgl', etc.) but figured that in the
>> long term this wouldn't be advantagous.  We feel that the situation is
>> analogous to QuickCheck: when the new version came out most people kept
>> using the old one until slowly the momentum shifted and more people
>> started using the new version (without checking in depth, Roel's Hackage
>> mirror reports QC-2.x now has 153 reverse dependencies as opposed to 127
>> reverse dependencies for QC-1.y).
> Just remember: you are now the maintainer of a package in the Haskell
> Platform, and that has some burden on ensuring stability and safety.
> API-breaking changes are fine, as long as well planned, and it may be up
> to 12 months before the HP can adopt an API changing release of a
> package.

Oh, we know that: we envisage it being a few months before anyone starts
using the new version of FGL.

One change I might make in a released version before then is if I'm
successful during AusHack in writing at least a start towards the
generic graph classes, we might make a 5.x release of fgl that has the
instances of the generic classes and then port at least graphviz over to
using the new generic classes.  I realise that these changes as well
won't necessarily go into the HP straight away, but it should help
improve cross-library usage down the track.

I was discussing the state of the graph libraries with Edward Kmett
yesterday, and here's what I said as what I envisage happening over the
next year or so:

* The generic graph classes will form a base library for accessing and
  using graphs.  It won't define any graph types itself, but will serve
  as a base compatability layer between libraries.  The focus of this
  will be a class I'm currently calling GraphLike which let's you access
  the vertices and edges of any type that matches the formal definition
  of a graph that it's a set of vertices V and a set of edges E such
  that forall e \in E, there exists two vertices v1, v2 \in V (not
  neccessarily distinct) such that there are two mappings "source e =
  v1" and "target e = v2" (or whatever you want to call them) between
  each edge and the set of vertices.

  Basically, this class is an accessor class, so it will work for things
  like package dependency graph in Cabal, etc. for graph-like types
  which it might not make sense to add or change vertices and edges in
  the graph.  Whether there will also be a class for adding/removing
  elements is currently up in the air, as this might not make sense for
  all graph types.  As such, those functions that don't need to edit
  graphs (e.g. graphToDot in graphviz) will be able to just use these.

* The set of FGL libraries will form an initial to intermediary layer of
  types.  If your problem isn't large and the inductive nature is
  applicable, then FGL will probably be your best bet.

* Edward's co-monadic graph library will be an intermediary to advanced
  layer; it sounds quite interesting but might not be as easy to use due
  to the types changing when you add a vertex, etc.

* fasta on #haskell{,-blah} has suggested that I read through the Boost
  Graph Library documentation and consider writing a graph library based
  upon that (and hints that he's once written a high-performance graph
  library in Haskell on this model).  As such, I'll have a look at this
  down the track during my copious free time :s (Edward thinks it might
  even fit in to his co-monadic approach, so we'll see).

What I'm after here is more "sharing" between graph types and libraries:
rather than defining something on just one specific graph type,
generalise it as much as you can (to avoid writing a new Graphviz
transformation library for every graph type for example).

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list