[Haskell-cafe] Library design question

Andre Nathan andre at digirati.com.br
Thu Sep 18 14:43:39 EDT 2008


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

  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

So I'm confused right now about how I should proceed. Any hints
regarding that?

Best regards,

More information about the Haskell-Cafe mailing list