[Haskell-beginners] Implementation question about directed acyclic graph

[Doug McIlroy]

Your suggested this representation
> type Connections = M.Map Int a [Int]
>
> data Graph a = Empty
>              | Gragh { nodes :: M.Map Int (Node a), nextID :: Int,
> connections :: Connections }


Making connections by name (in this case an Int) entails table
lookup at every step of any graph traversal. That is avoided by
this simple representation:
        data Graph a = Graph a [Graph a]
perhaps elaborated to allow the empty case
        data Graph a = Graph a [Graph a] | Empty
If you need node identifiers, e.g. to recognize repeat visits to
a node, they can be incorporated in data type a, or abstracted
into another field
        data Eq id => Graph id a = Graph id a [Graph id a]

Doug McIlroy