[Haskell-cafe] What do _you_ want to see in FGL?

[Henning Thielemann]

Ivan Lazar Miljenovic schrieb:

> Pros for allowing you to use a custom node type:
> * Matches your data better
> * No need for extra lookup maps when converting your data to FGL form
> 
> Cons:
> * Makes type-sigs uglier/more verbose

Unlabelled graphs with custom node type would have only one type
parameter. :-)

> * Restricts the ability to optimise

That's my question. As far as I know the set of node identifiers in a
graph is not contiguous, thus you cannot use Arrays but you must use
IntMap or so.

> Using Int gives us a fixed-size data type with known good comparison
> performance and with a range that should suit most purposes.

Replacing IntMap by Map is not much slower, is it?

> As an alternative, see how I have Graphalyze create an FGL graph from
> [n] and [(n,n,e)]:
> http://hackage.haskell.org/packages/archive/Graphalyze/0.9.0.0/doc/html/Data-Graph-Analysis.html#v%3AimportData
> 
> We're also considering using MPTCs or ATs to let you place restrictions
> on the label types (when defining a new graph instance).  However,
> before you again state how you don't want labels, consider this:
> 
> * It's easier to make a labelled graph act as an unlabelled one than the
>   other way around.

Sure, it's the same argument that in MatLab everything is a
complex-valued matrix. They even represent Bool by a 1x1 complex-valued
matrix. Possible, but clean? From today's viewpoint separation of
labelled and unlabelled graphs is additional work, but I'm afraid there
will arise problems with this design. Unfortunately, I can't tell them
today.

> The current "type Node = Int" alias is only there to provide a unique
> index type for referencing nodes; the actual Ints don't really represent
> the nodes IMHO, the labels do (in conjunction with the index for
> colouring, etc.).  In your example case of using PkgName (I assume you
> mean PackageName or PackageIdentifier?), can you guarantee that each
> PkgName value is unique before you go blindly using it (what about
> having the same library installed in both the global and user
> database?)?

Of course you must choose data as key, that is actually a key. But this
is not the problem of FGL. And with Node = Int, I also have to choose a
key for my dictionary (Map Something Node).
In my case I consider packages that are to be installed, so no
distinction between globally and locally installed packages. I want
really the package name as key.