functional graph

[Ron de Bruijn]

--- 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.
> 
> > About the graphs:Well, I never had graphs at
> 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
> anything about them.
> 
> > 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
it hard to start with it, because the most intuitive
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
to remember, which possibilities I already had.

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