[Haskell-cafe] A composable, local graph representation as an open discussion

[MarLinn]

Hi,

first of all, this is an interesting idea.

> Most functional algorithms for graphs use an edge-list
> with global labels.  Although effective, this method
> loses compositionality and does not exploit the type system
> for enforcing graph invariants such as consistency of the edge list.

I understand the argument, but aren't you are still using global labels? 
Or rather, global numbering. Doesn't that defeat the purpose?
Therefore I propose to replace
>> type Conn = Int
with

 > type Port = Int
 > data Connector l r = InternalConn Port | ExternalConn (Graph l r) Port

or maybe, to make organizing simpler

 > data Connection l r = Internal Port Port | Outgoing Port (Graph l r) 
Port | External (Graph l r) Port (Graph l r) Port

Now lookup via list traversals makes less sense, but then I would 
propose you store different types of connections separately anyway.


A second thing to note is that there seem to be only three general ways 
to implement graphs in Haskell (/purely functional languages): adjacency 
lists/matrices, tying the knot, or with native pointers through the FFI 
(I haven't seen that one in the wild though). You used the second 
approach, which is why updating the graph is hard. That doesn't mean 
your general approach of composing graphs can not be combined with the 
other two. In fact it looks like combining it with the "classical" 
adjacency lists should be as simple as throwing some IntMap operations 
together.

Cheers,
MarLinn