functional graph

Ron de Bruijn rondebruijn@yahoo.com
Tue, 15 Jul 2003 13:35:11 -0700 (PDT)

```--- Hal Daume <t-hald@microsoft.com> wrote:
> >> I think that the
> >> difficulties you are
> >> facing are from the fact that you are trying to
> >> express a purely
> >> functional "updatable" graph.
> >
> > Should I understand from this, that this is a
> > difficult problem and that there exist no easy way
> to
> > do this at the moment?
>
> Well, I think he was being a bit ironic.  You can
> either have a
> functional graph or an updatable graph, but not
> both.  It sounds like
> either would do and given that later in this message
> you discuss that
> you don't like imperativeness, then a functional
> graph (ala the
> Functional Graph Library -- FGL) would suit you
> perfectly.
>
> school
> > yet(first year student)... Although it is
> somewhere in
> > my textbooks...
>
> They're very simple.  You have a collection of
> nodes, N, and a
> collection of edges between elements of N.  Nodes
> and edges can have
> labels.  So for instance you could have Teachers and
> Classes as the
> nodes and the edges could be between the teacher and
> the class(es) which
> go together.
>
> > To solve my problem... I need an mutable array,
> but in
> > Haskell my program will then be unbelievable
> > imperative.
>
> No, you just need a graph :).
>
> > I have been following the discussion about the
> graph
> > and so, but the arrow classes and so on, are like
> > something too sophisticated for me at this moment
> I
> > think, although I have some idea of how they work,
> I
> > really don't know when to apply them. I just found
> > out, how Monads work, so...
>
> THe discussion about arrows is a complete
> divergence.  You don't need
>
> > But I certainly believe that my problem must be
> fixed
> > before it's easy to program in Haskell.
>
> Theorem: this problem is already fixed.
> Proof: it is easy to program in Haskell.  QED.
>
> :)
>
>  - Hal

I have read the chapter in my textbook :) and I have
read and played with the FGL module.

I must say the FGL module looks impressive, but I find
way of doing it for me was, to have different
datatypes for Teacher Subject and so on.

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.

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) ?

The second intuitive solution is to take a datatype
like
data GraphNode|Teacher etc
|Subject etc
|Student etc

Should this be the way to do it?

And then yet another question: I need some kind of way

In example in my C++ program I used a couple of
array's with in each array pointers to the
StudentObjects, TeacherObjects.

So I had the notion of the first teacher, the second
teacher, the third and so on(in 0(1)), although I only
need the notion of did I test this possibility and
give me the next of Student/Teacher/whatever.

I must be able to put it somewhere, but where?
In the Graph itself there isn't really space for it,
unless I create a complete timetable in the beginning
with all Studentnodes pointing to this first teacher.
But now I have to be able to change the Graph in such
a way that I can change the first node where an
error(schedulingerror) occurs, (for example a "room is
full" error) to let the Student point to the next
room(see the notion above).

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

Greets Ron

__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only \$29.95 per month!
http://sbc.yahoo.com

```