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

[Heinrich Apfelmus]

Ivan Lazar Miljenovic wrote:
> Heinrich Apfelmus writes:
>> I'm not sure what the right solution is, but I think it definitely
>> involves catering for different node types. For instance, the library
>> could operate on a type
>>
>>     newtype Graph node a b = Graph (Gr a b, Data.Map.Map Int node)
>>
>> or it could offer a more useful  NodeMap  type and make the  Node  type
>> abstract. Some systematic and simple abstractions to manage nodes is
>> needed anyway.
> 
> As I said, we're considering using an Associated Type to let users
> choose what type they want to use (probably with a default Map instance
> for this).  However, we'd recommend/push the Int-based one.

For my  make  example, I prefer a plain parameter because it would be
too verbose to define a new class that has  FilePaths  as node types.
I'd use the  Int  instead, but this defeats the point: why offer
flexible node types when it's too much of a burden to use them?

> An explicit type parameter for the vertex type is not appropriate for
> this reason: you don't want to change it.

It's true that I don't want to change the node type, but I want to curry
it. If I don't feel like writing out the node type every time, I can use
a type synonym:

   type MyGraph a b = Graph FilePath a b


Graphs with different node types don't behave differently; graphs are
parametric with respect to the node type, just like lists don't behave
differently on different element types.


>> Also, hard-coding  Node = Int  feels like the wrong kind of flexibility:
>> the user is able to do anything with it, just in case the library forgot
>> some important functionality. Which is exactly what happened in my case
>> when I used  Map.findIndex . I prefer the library to get it right.
> 
> What do you mean by "the library forgot some important functionality"?

Ah, I'm comparing  Node = Int  to a  Node  type that is entirely
abstract. After all, conceptually,  Node  is not an integer, it's a
unique identifier.

If  Node  is abstract, then you will probably miss things like the [1..]
 that you mentioned.

Nonetheless, I would like to see  Node  to become abstract. This means
that the graph library should include a library that deals with unique
identifiers  Node . The [1..] pattern would correspond to a function

    freshNodes :: () -> [Node]

>> PS: While we're at it, I think  newNodes  should return an infinite list
>> of  Node  instead of requiring a fixed number to be specified in
>> advance?
> 
> Well, if we let the vertex type be _anything_ (that is an instance of
> Ord; we'll probably require that much at least, though maybe just Eq
> would make sense for list-based graphs), then how do we generate
> newNodes?  Require Enum?  Bounded?

Ah, that suggestion was for  Node = Int  or  Node = abstract . If the
library user uses his own node type, it's him who is responsible for
allocating new  Nodes .

> Really, performance aside, this is my biggest possible problem with
> generic label types is that it may make it harder to define various
> algorithms on graphs because you can no longer guarantee what you can do
> with the vertex types; as such people may resort to requring the vertex
> type to be Int or something to use a specific algorithm.

Ah, you mean algorithms that create new nodes on the fly? I don't think
that  Node = Int  works for them either, because the user might have his
own ideas about which  Ints  can appear as graph vertexes. For instance,
he might only use even numbers to denote vertexes and will be surprised
by a library algorithm that suddenly creates odd vertexes. In short,
Node  needs to be abstract for that.

Other than that, I don't see much of a difference between custom vertex
types and  Int  . Internally, you can always use  Int  to reference
nodes and keep the association between the custom vertex type and  Int
in a separate map, like this

   data Graph node a b =
       Graph { internal :: Gr a b , nodes :: Map node a }


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com