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

[Heinrich Apfelmus]

Ivan Lazar Miljenovic wrote:
> Heinrich Apfelmus writes:
>> I'd be happy with either one. :) In both cases, I want to specify a
>> custom vertex type.
> 
> Except an abstract type isn't a custom vertex type...
> 
>> I can either do that directly if the library permits, though I think the
>> solution with associated types is too cumbersome to be useful for my
>> make  example.
> 
> Why?

I was under the impression that I would have to define a new graph data
type with  FilePath  as vertex type and make that an instance of  Graph
? In that case, it would be much shorter for me to stick with the clumsy

        nodeMap = Map.fromList nodes
        index k = Map.findIndex k nodeMap
        nodes'  = map (\(a,b) -> (index a, b)) nodes
        edges'  = map (\(a,b,c) -> (index a, index b, c)) edges

>> Or I get an abstract  Node  type and the library provides just the right
>> functions that make it easy to manage a custom vertex type myself. I had
>> hoped that the  Data.Graph.Inductive.NodeMap  module provides this,
>> which it doesn't.
> 
> Not sure I follow what you're saying here; then again, my graph stuff
> has typically been to create the graph and then do stuff to it _as_ a
> graph (and not wanting/needing to get a specific node based upon its
> label, etc.).

In the  make  example, I didn't need to get a node based on its label
either. But the graph was a graph of  FilePaths  and I still have to
implement an association between that and  Int . (In fact, I don't know
of any graph whose nodes are unique integers conceptually.)

In other words, I have to make sure that every  FilePath  is mapped to a
unique integer which I can then glue into a graph. This is not hard to
do with a  Data.Map  and the four lines of code above do exactly that.
However, I still had to think about it and it took me way too long to
come up with these four lines. What I would like to see is that the
*library* has thought about that for me already.

A good way to ensure that the library has thought about that is to make
the  Node  type abstract. This way, the library has to provide the
functionality to create and manage nodes, which I would otherwise cobble
together on my own by messing with  Int .

One possibility is to offer a function

    mkGraph :: Ord node => [(node,a)] -> [(node,node,b)]
            -> (Gr a b, NodeMap node)

that accepts a custom vertex type, creates all the necessary unique
integers internally and also returns an association between the newly
created  Nodes  and the custom  node  in case I want to refer to the
nodes in the graph with the custom type.

The  NodeMap  type - while implemented as a  Data.Map - is abstract as
well and has the primitives

   empty      :: NodeMap n
   insert     :: n -> NodeMap n -> NodeMap n
   lookup     :: n -> NodeMap n -> Maybe Node
   lookupNode :: Node -> NodeMap n -> Maybe n
   delete     :: Node -> NodeMap n -> NodeMap n

This is all you need to manage the association  node <-> Node . In
particular,  insert  creates new  Nodes  on the fly.

And since the nodes in the graph and the  NodeMap  will usually come in
pairs, we can as well give the pair a new name:

   type Graph node a b = (Gr a b, NodeMap node)


To summarize: an abstract  Node  type relieves me from thinking about
the association between my conceptual node type and unique identifiers.
I'd be happy with anything along these lines, the interface above is
just a suggestion.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com