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

Henning Thielemann schlepptop at henning-thielemann.de
Wed Apr 28 06:39:47 EDT 2010

Ivan Miljenovic schrieb:

> So you don't want the labels to be part of the actual datatype?  And
> for users to then have to deal with any labels they want themselves?

No, you would continue to provide labelled and unlabelled graphs, where
unlabelled graphs (or just Graphs) are the base type and labelled graphs are

data LabelledGraph node edge =
   LabelledGraph Graph (Map Node node) (Map (Node,Node) edge)

This is a matter of separation of concerns. Sure, it means that you need
to split the graph algorithms into their parts: each algorithm into an
unlabelled and a labelled part. If there are algorithms that make no
sense on labelled graphs, then you need only the first part.

> If so, I don't think this is feasible; some of the nice parts of FGL
> IMHO are how it deals with labels (admittedly, I've had to write and
> use my own "((Int,a) -> a') -> g a b -> g a' b" function because it
> doesn't have one...).  Removing this would be a step backwards.
> How exactly is it bad/a pain to have to deal with specifying "g ()
> ()", especially since there are some pre-defined "unlabelled" graph
> type and function aliases?

For problems that do not need labels, why shall I cope with them?
I expect that you quickly run into the need for type extensions, if you
define a graph type class that have only unlabelled graphs as instance.
For instance:

> instance SpecialGraph (gr () ()) where

is not Haskell 98, instead

> instance (IsUnit a) => SpecialGraph (gr a a) where
> class IsUnit a where toUnit :: a -> ()
> instance IsUnit () where toUnit = id

would be Haskell 98, but is certainly more complicated.

This may also answer your question, how hard you should try to stay
Haskell 98. My experience is, that with a proper design of a library you
can reduce the need for type extensions. This makes your code more
portable and easier to understand.

More information about the Haskell-Cafe mailing list