[Haskell-beginners] Things which predictedly change over time

[Twan van Laarhoven]

First of all, I would separate the mathematical description of the problem from 
issues about optimization such as "without having to enumerate all days and 
check each day individually". First make a specification, and make it correct. 
You can worry about optimizations later.

So what would a specification for a schedule be? You already suggested a list of 
pairs. Something like

     type ScheduleSpec event = [(DateTime,event)]

For trains the situation is more complicated, because a single train has a 
schedule of where it will be at what time, and there can be multiple trains. So 
then you get

     data Train = { trainStops :: [(DateTime,Place)], trainInfo :: MoreStuff }
     type TrainSchedule = [Train]
     -- or maybe use relative time for the stops, I'm not sure

Now you implement your queries on this datatype. For specifying schedules you 
could think of combinators like

     -- union of two schedules
     (<>) :: Schedule -> Schedule -> Schedule
     empty :: Schedule
     -- a schedule with a single train
     singleton :: Train -> Schedule
     -- a copy of the train runs every day until the end of days
     everyDay :: Schedule -> Schedule
     everyHour :: Schedule -> Schedule
     -- trains no longer depart after the given date
     untilDate :: DateTime -> Schedule -> Schedule
     untilTime :: TimeOfDay -> Schedule -> Schedule
     -- trains don't run on the given day of the week
     notOnDay :: DayOfWeek -> Schedule -> Schedule
     -- etc.

*If* the code that uses lists turns out to be too slow for you, you can think 
about turning the TrainSchedule into something more complicated. I would still 
keep the unoptimized version around, since it gives you something to compare and 
test against. A more complicated type could be

     data Schedule
         = Single Train
         | Union [Schedule]
         | Repeat Schedule TimeDiff
         | IfThenElse Condition Schedule Schedule

Whether this work any better depends on your application, your schedules, etc.


Twan

On 17/01/13 21:34, Martin Drautzburg wrote:
> Hello all,
>
> ... and I thought this was easy:
>
> find a way to represent a "schedule", i.e. a thing which assumes different
> values at different days.
>
> It turned out I don't know what a schedule is. What is the formalism behind
> "This train leaves at 11:00 every day except sundays (where it doesn't run at
> all), except on Easter Sunday where it leaves at 11:10"?
>
> I do not even need to know the "most compact" representation, just some
> representation which is reasonably compact and which can be translated into
> human language.
>
> So far I believe a Schedule is a function which takes a day and retuns a
> Value. If I had this function, I could easily list values for all days within
> given interval of days.
>
> But the inverse should also be possible. Given a List of (Day, Value) pairs, I
> should be able to construct a Schedule.
>
> The reason why I am interested in this is the following:
>
> "On every Monday I take a trip from A to C. To do so, I need to take two
> trains and change trains in B".
>
> So I have to consider the two train schedules to decide whether or not my
> itinerary will work. So I kind of have a Constraint which is scheduled itself
> (every Monday) and which depends on two other Schedules. The Constraint can be
> satisfied for some days and violated for others. I want to find out when it is
> violated (within a finit interval of days) without having to enumerate all
> days and check each day individually.
>
> And most importantly I want to specify the Constraint without referring to
> individual days, just like I did in the quoted sentence above.
>
> You may also say, I want to lift the fine world of relational algebra to a
> world where things change over time, i.e. assume different values at different
> days.
>
> This seems to be such a common planning problem! You face it every time you
> deal with things which are not constant over time, and it becomes a nightmare
> when you deal with relationships between them. Still I could not find anything
> useful on the net. How can the world turn at all without having this solved?
>
>
>