functional graph

Hal Daume t-hald@microsoft.com
Tue, 15 Jul 2003 14:02:49 -0700


> But it looks the Graph class works on types a and b
> where a is the Node type where b is the Edge type, or
> just the other way around :), I don't have the code
> right now.

Yes, 'Graph n e' is a graph whose nodes are labelled with elements of
type n and whose edges are labelled with elements of type e.

> The above rules out my way of representing the data,
> or doesn't it (i.e. is there some fancy, magical way
> of doing this) ?=20

Yes.  (I.e., it rules it out.)

> The second intuitive solution is to take a datatype
> like=20
> data GraphNode|Teacher etc
>               |Subject etc=20
>               |Student etc
>=20
> Should this be the way to do it?

Yes.

> And then yet another question: I need some kind of way
> to remember, which possibilities I already had.
>=20
> In example in my C++ program I used a couple of
> array's with in each array pointers to the
> StudentObjects, TeacherObjects.=20

You could use the same here, or use a FiniteMap.  If i'm understanding
you correctly you miss the fact that there's no way to look up a node
given it's label.  This is because the graph module doesn't assume that
node labels are unique (otherwise it wouldn't need to generate the Node
labels itself).

I generally bundle a 'Graph n e' together with a 'FiniteMap n Node' so
that I can look up Node identifiers based on node labels.

> But then I yet have another problem. How can I
> guarantee, to do a complete path traversal, each time
> in exactly the same way?

I don't understand what you mean.  In your case, what is a "complete
path traversal."

Regardless, if you have the same graph and the same functions for
traversing it, since Haskell is referentially transparent you should
also "traverse it in the same way..."

 - Hal