[Haskell-cafe] Library design question

minh thu noteed at gmail.com
Thu Sep 18 15:13:55 EDT 2008


2008/9/18 Andre Nathan <andre at digirati.com.br>:
> 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


More information about the Haskell-Cafe mailing list