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?