Re: [Haskell-beginners] Implementation question about directed acyclic graph

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