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

[Ivan Lazar Miljenovic]

Heinrich Apfelmus <apfelmus at quantentunnel.de> 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.

> 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"?

> 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?

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.

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com