Representing cyclic data structures efficiently in Haskell

[Sarah Thompson]

>>From reading your message, it seems you want a graph library of sorts.
>
The important bit is 'of sorts', unfortunately! Most graph libraries 
I've seen to date (although I must admit that they have been written in 
C and C++, including one I perpetrated personally) don't really work 
that well for circuits because, for anything other than trivially simple 
components, the connections between nodes need to be labelled.

A component representing something simple like (say) an 'and' gate would 
be easy enough to represent as a node of an ordinary directed graph. In 
such a case, an incoming arrow would always be an input of the gate, and 
an outgoing arrow would always be the output. I need to be able to 
represent more complex components, up to and including the complexity of 
things like CPUs, where you might have lots and lots of inputs and 
outputs with substantially different meanings. In the case of a CPU, it 
would never be acceptable to (for example) swap a chip select output for 
an address or data line.

This makes me think that an off-the-shelf graph library won't quite be 
what I'm after, so I will almost certainly need to write the code. What 
I'm more interested in at the moment is a view on the best kinds of 
approach that might be appropriate.

I'd considered something like embedding the type in the IO monad, with 
links between components implemented as IORefs, but I'd really prefer 
something cleaner (pure functional). If the code ends up horribly 
complicated in order to get decent performance, I might as well fold and 
use C++ instead.

I'm currently wondering about going for an adjacency list approach (as 
used by most graph libraries), with the tuples in the adjacency list 
extended to include input/output labels, resulting in a 4-ary tuple 
rather than the usual 2-ary. But, I don't want to be stuck with 
representing this as a list -- I really need log N lookups or 
performance will stink horribly as circuits get big. Maybe a pair of 
finite maps, allowing the edges to be traversed in either direction?


>If FGL seems like overkill to you, I have my own little mini graph
>library which basically looks like:
>
>  - An ADT, Node:  newtype Node = Node Int deriving ...
>  - The 'Graph n e' data structure, containing:
>      - a FiniteMap from n -> Node
>      - an (growable?) array of type IOArray (Node,Node) e
>
>the array represents the edges in the top half (i do some index fiddling
>to get this efficient) and the finitemap represents the node labellings.
>It's a pretty stupid interface and works a lot better when the graphs
>are fixed size (that way you don't need to grow the array).  But it
>works.
>  
>
The finite map from n to Node seems like a good idea. Does representing the adjacency list as a flat array cause any problems?

Sarah

-- 
     ----------------------------------------------
    / __            + / Sarah Thompson      **** /
   / (_  _  _ _ |_   /                        * /
  /  __)(_|| (_|| ) / sarah@telergy.com      * /
 / +               / http://findatlantis.com/ /
----------------------------------------------




-- 
      ----------------------------------------------
     / __            + / Sarah Thompson      **** /
    / (_  _  _ _ |_   /                        * /
   /  __)(_|| (_|| ) / sarah@telergy.com      * /
  / +               / http://findatlantis.com/ /
 ----------------------------------------------