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