[Haskell-cafe] Suggestion for Data Structure regarding Timetabling and Time Intervals

[Michael Roth]

I would like to experiment with timetabling algorithms and resource 
scheduling in a special use case: I have time intervals like A, B and C 
and they are put sequentially on a time line.
However, between the major time intervals like A, B etc. their are 
always "minor" time intervals which separates the major ones. For example:

     a, A, ab, B, bc, C, c

Upper case letters denotes "major" time intervals and lower case letters 
denotes the minor intervals which always separates the major ones.

The minor time intervals only have a duration, their exact occurrence in 
time doesn't matter, only the fact that they occur between the major 
time intervals are important.
The major time intervals start and stop a specific time; they don't 
overlap and maybe there is free time between major and/or minor time 
intervals.
The minor time intervals "a" and "b" at the beginning and ending of the 
complete time line I'm not interested in and can be omitted completely.


Say, to insert a time interval X after B, assuming there is enough free 
time between B and C, the resulting structure is:

     a, A, ab, B, bx, X, xc, C, c

The minor time interval "bc" is discarded and two new minor time 
intervals "bx" and "xc" are inserted.


I'm a little bit stuck what a good data structure would be for this 
problem. Additionally I would like to use an infinite data structure, 
because a priori I don't know how many time intervals have to be created 
and inserted into the time line.
The time intervals are not generated in an ascending order. An algorithm 
will search for possible places to insert the new created major time 
intervals and creates the corresponding minor time intervals.
There is the concept of a "present time" in this process. The algorithm 
can only manipulate the future. I thought to push all time intervals in 
the past respective to this "present time" to a MonadWriter to get my 
infinite list of time intervals. The "present time" is moved forward at 
specific events.


What do you experts think about the approach with the MonadWriter? What 
would be a good data structure to ensure that all major time intervals 
are separated by minor time intervals?


Thank you in advance for your ideas and comments,


Michael Roth