2008/9/18 Andre Nathan
Hello
I'm trying to write a simple graph library for a project of mine (actually, I'm porting it from OCaml) but I've got a design question right in the beginning.
My Graph type is the following.
data Graph a b = Graph { adjacencies :: Map Int (a, (Map Int b)) , numVertices :: Int , numEdges :: Int }
Types "a" and "b" refer to vertex and edge labels (I know it's kind of weird to use a Map of Maps to represent a graph, but it helps me removing vertices later, which is something I'll need to do.)
Creating an empty graph is trivial:
empty :: Graph a b empty = Graph Map.empty 0 0
The issue I hit was when writing the function to add a vertex to the graph. Since I need to update the vertex counter, I've used the state monad:
addVertex :: Int -> a -> State (Graph a b) () addVertex vertex label = do g <- get let adj = Map.insert vertex (label, Map.empty) (adjacencies g) put $ g { adjacencies = adj, numVertices = numVertices g + 1 }
That works fine, but from the point of view of a user of the library, the addVertex function should take a "Graph a b" as its first argument, as one would expect to be able to say which graph is going to be modified.
So I'm confused right now about how I should proceed. Any hints regarding that?
Hi, Why not simply addVertex (Graph adj nv ne) vertex label = Graph (Map.insert ...) (nv+1) ne ? If you don't want to pattern match because you expect you Graph data type to change later, you can instead use addVertex g vertex label = Graph (Map.insert ...) (nv+1) ne where adj = adjacencies g nv = numVertices g ne = numEdges g If you need the one inside the State monad, you can reuse the new version of addVertex. Or, why do you want the user of your library give the graph as an argument if that argument is implicit (because it is inside the State monad) ? Hope this helps, Thu