# Representing cyclic data structures efficiently in Haskell

Graham Klyne GK@ninebynine.org
Mon, 07 Jul 2003 19:03:25 +0100

```Lazy evaluation means that you can embed nodes directly in a cyclic
structure, even though that would appear to create an indefinite
regression.  In order to detect cycles, one might add a node
identifier.  Here's a simple example:

[[
-- spike-cyclicstructure.hs

data Node = Node { nodeid :: String, adjacent :: [Node] }

instance Eq Node where n1 == n2 = nodeid n1 == nodeid n2

instance Show Node where show = nodeid

findPaths :: Node -> Node -> [[Node]]
findPaths fromNode toNode = map reverse \$ findPaths1 [] fromNode toNode

findPaths1 :: [Node] -> Node -> Node -> [[Node]]
findPaths1 beenThere fromNode toNode
| fromNode == toNode = [fromNode:beenThere]
| otherwise = concat [ findPaths1 (fromNode:beenThere) nextNode toNode
, not ( nextNode `elem` beenThere ) ]

n1 = Node "n1" [n2,n3,n4]
n2 = Node "n2" [n1,n3,n4]
n3 = Node "n3" [n1,n2]
n4 = Node "n4" [n1,n2]

test1 = findPaths n1 n2 -- [[n1,n2],[n1,n3,n2],[n1,n4,n2]]
test2 = findPaths n1 n3 -- [[n1,n2,n3],[n1,n3],[n1,n4,n2,n3]]
]]

behaves in some ways like a pointer to that value in (say) C.

If you don't want to assign unique identifiers by hand, you could use a
state transformer monad to generate them for you.

#g
--

At 16:37 07/07/03 +0100, Sarah Thompson wrote:

>> 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
>
>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
>
>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/ /
>----------------------------------------------
>
>
>_______________________________________________