[Haskell-cafe] A composable, local graph representation as an open discussion
monkleyon at googlemail.com
Tue Oct 25 13:55:07 UTC 2016
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
> 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
More information about the Haskell-Cafe